筛选从0-1亿的素数,使用JavaScript实现。

运行环境:macOS High Sierra,10.13.6,2.3 GHz Intel Core i5,8 GB 2133 MHz LPDDR3,sublimeText控制台。

低效法:

let loopCount = 0;
let count = 100000000;
let checkNumCount = 0;

console.time("sort1");
let arr = [];
for (let i = 0; i < count; i ++) {
   if (i >= 2) {
      if (i === 2 || i === 3) {
         arr.push(i);
      } else {
         checkNumCount ++;
         let isPrime = true;
         for (let j = 2; j <= Math.sqrt(i); j ++) {
            loopCount ++;
            if (i % j === 0) {
               isPrime = false;
               break;
            }
         }
         if (isPrime) {
            arr.push(i);
         }
      }
   }
}
console.log(arr.length, loopCount, checkNumCount);
console.timeEnd("sort1");

高效方法:

console.time("sort2");
arr = [];
loopCount = 0;
checkNumCount = 0;
for (let i = 0; i < count; i ++) {
   if (i >= 2) {
      if (i === 2 || i === 3 || i === 5 || i === 7 || i === 11 || i === 13) {
         arr.push(i);
      } else {
         if (i % 2 !== 0 && i % 3 !== 0 && i % 4 !== 0 && i % 5 !== 0 && i % 6 !== 0 && i % 7 !== 0 && i % 8 !== 0 && i % 9 !== 0 && i % 10 !== 0 && i % 11 !== 0 && i % 12 !== 0 && i % 13 !== 0 && i % 14 !== 0 && i % 15 !== 0) {
            checkNumCount ++;
            let isPrime = true;
            for (let j = 2; j <= Math.sqrt(i); j ++) {
               loopCount ++;
               if (i % j === 0) {
                  isPrime = false;
                  break;
               }
            }
            if (isPrime) {
               arr.push(i);
            }
         }
      }
   }
}
console.log(arr.length, loopCount, checkNumCount);
console.timeEnd("sort2");

运行结果:

//参数依次为获取到的素数个数,进行的循环总次数,进入循环的整数个数,运行时间
5761455 46524124248 99999996
sort1: 162929.460ms
5761455 46351307110 19180819
sort2: 161345.078ms
[Finished in 324.4s]

从运行结果来看,高效法的循环次数比低效法少了1.7亿,check的整数个数差不多为原来的1/5,时间减少了1584.392ms,将近总时间的10%,效率还是有提升的,但不是很大。

在高效法中,我们把所有的2-15的倍数的数过滤,此处用的是if方法,而不是for方法,如果用for,则会增加循环次数,增加消耗,为什么是到15,亲测在我的机器上,到15是比较快的,少一个多一个都会增加时间,在不同的环境中可能会有不同。

有什么问题可以在下方留言。

性感码农,在线解答。

发表评论

电子邮件地址不会被公开。 必填项已用*标注