版权声明：
尊重知识产权，严厉打击非法采集。
Javascript 求素数的两种算法
请尊重原创，本文原文地址：https://hooyes.net/p/javascript-prime-number
素数
质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数。
场景
求一定范围内的素数，例如求小于10的素数(2、3、5、7)。
那么如何求小于 N 的素数呢？
方法一：试除法
这种方式很传统理解上也简单，给定一个范围，那么就逐个循环去试除小于它数。
现在我们假设 N 等于 120
let N = 120;
let primes = [];
// 用于存素数结果集
loop:for(let x=2;x<=N;x++){
for(let k=2;k<x;k++){
if(x%k==0) continue loop;
//一旦有被小于它的数整除，则退出试下一个数
}
//能走到这一步的就是素数了
primes.push(x);
}
console.log(primes.join(','))
/*
得到小于N的素数集合
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113
*/
很显然，每个小于N的数都要跟它前面的数去除一遍，这种方法不是最高效的。
方法二：筛法
筛法的思路来源于 埃拉托斯特尼筛法
先把所有2的倍数去掉，然后剩下的那些数里面，最小的是3，3就是素数，然后把3的倍数都去掉，剩下的数里面，最小的是5，所以5也是素数…（可以看出已跳过4的试除，越多到后面跳过的数越多)
上述过程依次进行，但不像试除法逐个进行，就可以把某个范围内的非素数全都除去，剩下的就是素数了。这种方式的好处在于运算不重复，高效。
有一张很形象的动画，能直观地体现出筛法的工作过程。
（非素数就像被筛子筛掉一样）
let N = 120;
let primes = [];
// 用于存素数结果集
let nums = [];
// 待筛选的数据集
for(let x=2;x<=N;x++){
//hooyes提示：此处初始化的时候，也可直接筛掉2的倍数数据减半。
//if(x%2!==0)
nums.push(x);
}
// 递归函数
function PrimeFn(data){
let p = data.shift();
// 数组最前端的一个数即素数，拿出来存起，并作为下次筛除的分母。
primes.push(p);
let t = [];
for(let v of data){
v%p!==0 ? t.push(v) : ""
// 能被 p 整除的都筛除掉，不能整除的放到临时数组t存起来。
}
// t 是下次待筛数组，元素个数会越来越少，若还有就进行一次递归。
t.length>0 ? PrimeFn(t) : ""
}
PrimeFn(nums);
console.log(primes.join(','));
/*
得到小于N的素数集合
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113
*/
总结
//关于试除法，通俗易懂不需要太多解释了。
//关于筛法求素数，是Hooyes按照埃拉托斯特尼的思路花了周杰伦一首歌的时间写的，若有不足之处或更优的算法请指教。
//转载请注明出处。
$ welcome to hooyes.net
[INFO] ------------------------------o-
[INFO] Author : HOOYES
[INFO] Site : https://hooyes.net
[INFO] Page : https://hooyes.net/p/javascript-prime-number
[INFO] Last build : 2023-07-31 09:16:20 +0000
[INFO] -0------------------------------
原文地址：https://hooyes.net/p/javascript-prime-number
原文地址：https://hooyes.net/p/javascript-prime-number
Content
...