关于快速获取N个质数算法

背景来源于很久前组内的一次讨论,如何可以更高效的获取N个质数。
使用场景是很久前在对选择商品多属性SKU的情况下,选中某些属性的情况下,判断其它属性的选中状态,通过质数的方式来做可选操作判断。
关于质数方案原文应该是出在淘宝某团队,这里只讨论关于获取质数的一些方法

纯粹循环

这种方法是最容易理解和想到的方法,依次从2到当前数字,如果任意一个能被整除那就不是质数
首先来提供一个测试方法,通过传入一个方法验证10万内的所有质数,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* GLOBAL js */
window.getPrimeNumArr = (fn, n = 10 * 10000) => {
console.time(fn.fnName);
const primeNumList = [2];
for (let i = 3; i < n; i++) {
if (fn(i, primeNumList)) {
primeNumList.push(i)
}
}
console.timeEnd(fn.fnName);
console.log(primeNumList);
console.log(`${n}共有:${primeNumList.length}个`);
console.log('--------------------');
return primeNumList;
}

纯粹循环判断是否为质数的方法:
1
2
3
4
5
6
7
8
9
10
function isPrimeNum(num) {
for (let i = 2; i < num; i++) {
if (num % i === 0) {
return false;
}
}
return true;
}
isPrimeNum.fnName = '纯粹循环';
getPrimeNumArr(isPrimeNum)

点击上面代码块 运行单个 按钮,纯粹循环大概要消耗2s的时间。

整除质数

只用需要判断的数字去除以已有的质数,计算是否可整除,都不能被整除的就为质数。

1
2
3
4
5
6
7
8
9
10
function isPrimeNum2(num, list) {
for (let i = 0; i < list.length; i++) {
if (num % list[i] === 0) {
return false
}
}
return true
}
isPrimeNum2.fnName = '整除质数';
window.getPrimeNumArr(isPrimeNum2);

点击运行全部,可以看到对比第一种方法速度已经提升了大概10倍,当然还可以更快看下面的方法

开平方

需要判断的数字进行一次开平方计算,然后判断开平方后的数字是不是可以被小于他的数字整除

1
2
3
4
5
6
7
8
9
10
11
12
// 开平方
function isPrimeNum3(num) {
const sqrt = Math.floor(Math.sqrt(num))
for (let i = 2; i <= sqrt; i++) {
if (num % i === 0) {
return false;
}
}
return true;
}
isPrimeNum3.fnName = '开平方';
window.getPrimeNumArr(isPrimeNum3);

点击运行全部,对比第一种方法已经提升了100多倍的速度

结合开平方和整除质数

上述两种方法的结合版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 开平方加已存在的质数
function isPrimeNum4(num, list) {
const sqrt = Math.floor(Math.sqrt(num))
for (let i = 0; i < list.length; i++) {
if (list[i] > sqrt) {
return true;
}
if (num % list[i] === 0) {
return false;
}
}
return true;
}
isPrimeNum4.fnName = '开平方+整除质数';
window.getPrimeNumArr(isPrimeNum4);

速度对比前一种方法,又有了1倍的提升。

小结

从最原始的方法都后面优化过得算法性能提升了大概200多倍,至于每种算法原理和复杂度分析等下次再来补上吧。
虽然在日常开发中我们很难遇到这种需要大量计算的场景,但关注更优的实现对自己的要求高一点总是好事。