我也不知道为啥,突然想写这个算法,以前也写过,现在用 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
}
测试了一下,似乎是对的。
好吧,自己写的都挺晕的。
![](https://img.haomeiwen.com/i25078225/41c51615a17961d7.png)
大概对吧。
运行的时候cpu并没有占满,因为单线程吗?
网友评论