hooyes 灵感纵容非凡

Javascript 求素数的两种算法

2016-08-08
hooyes

素数

质数(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的试除,越多到后面跳过的数越多)

上述过程依次进行,但不像试除法逐个进行,就可以把某个范围内的非素数全都除去,剩下的就是素数了。这种方式的好处在于运算不重复,高效。

有一张很形象的动画,能直观地体现出筛法的工作过程。 (非素数就像被筛子筛掉一样) Hooyes-图1

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按照埃拉托斯特尼的思路花了周杰伦一首歌的写的,若有不足之处或更优的算法请指教。

 //转载请注明出处。


Similar Posts

Content
TOP