美文网首页前端开发那些事儿
写一个在指定范围内筛选素数的算法

写一个在指定范围内筛选素数的算法

作者: 自然框架 | 来源:发表于2021-07-17 10:03 被阅读0次

我也不知道为啥,突然想写这个算法,以前也写过,现在用 js 重新写一下,避免老年痴呆。。。

筛选法的优点

  • 速度快
  • 代码简单

筛选法的缺点

  • 只能在指定的范围内去筛选,超出范围就不行了。
  • 范围和变量的范围有关
  • 速度和电脑的性能有关

思路

  • 建立一个数组,存放初始素数
  • 存放 > 10 且 < 指定范围的奇数(因为偶数都不是素数,就不放了)
  • 删掉素数的倍数
  • 到最大的范围的开平方即可。

编码

定义两个指针,第一个(i)指向首位的素数,第二个(j)指向要判断筛选的数,移动第二个指针依次判断,是倍数则删除。(用累加的方式实现倍数,避免乘法)

到末尾后,第一个指针指向下一个素数,第二个指针指向下下一个数。

第一个指针指向 最大范围的开平方 即可停止。
筛选完毕。

// 在指定范围内筛选素数
const find1 = (endNumber) => {
  const arr = [2, 3, 5, 7, 11]
  // 初始化
  for (let i = 13; i < endNumber; i += 2) {
    arr.push(i)
  }
  const kaifang = parseInt(Math.sqrt(endNumber))
  // 去掉素数的倍数
  for (let i = 1; i < arr.length; i += 1) {
    if (arr[i] < kaifang) {
      // 获取基数
      const a = arr[i] // 3 开始,去掉其倍数
      let cpp = a + a // 6 倍数
      for (let j = i + 1; j < arr.length; j += 1) {
        if (arr[j] === cpp) {
          // 删掉
          arr.splice(j, 1)
          cpp = cpp + a // 倍数
        }
        if (cpp < arr[j]) cpp = cpp + a // 倍数
      }
    }
  }
  return arr
}

测试了一下,似乎是对的。
好吧,自己写的都挺晕的。

部分素数

大概对吧。

运行的时候cpu并没有占满,因为单线程吗?

相关文章

  • 写一个在指定范围内筛选素数的算法

    我也不知道为啥,突然想写这个算法,以前也写过,现在用 js 重新写一下,避免老年痴呆。。。 筛选法的优点 速度快 ...

  • 素数算法

    寻找素数的算法有很多,最著名应是筛选法,以下是笔者用JavaScript编写的一个找素数的函数,借鉴了各种找素数的...

  • RSA加密解密算法—数论基础

    本章涉及知识点1、素数的定义2、寻找素数算法—短除法3、寻找素数算法—筛选法4、互质关系5、欧拉函数的证明6、欧拉...

  • 2019-03-24

    今天写下来,关于筛子算法,计算素数,针对大数的判断。简单写一下算法,假设计算40000以内的素数。 筛子算法, 百...

  • Algorithm

    素数筛选

  • 区间素数线性筛选

    区间素数线性筛选 假设应用场景为求一个区间长度远小于右端点的所有素数,该区间为 。如若使用朴素素数线性筛选,则需...

  • 素数筛选

    今天在面试时被问到了一个问题:求不大于n的最大素数,当时只想出暴力解法,回来查资料找到了正确的求解方法。 素数筛法...

  • 筛选素数/筛选质数

  • 素数线性筛选

    素数线性筛选 素数的定义是除了1和自身能被整除外,没有其他数能被它整除。除此之外,1既不是素数,也不是合数。因此,...

  • Android 每日算法:猫扑素数、单词反转

    经典算法集锦,不定时更新 一、素数(质数)算法 定义: 质数(prime number)又称素数,有无限个。质数定...

网友评论

    本文标题:写一个在指定范围内筛选素数的算法

    本文链接:https://www.haomeiwen.com/subject/dbnbpltx.html