其他
质数判定的几种方法及性能优化
文章内容
素性测试 (Primality test)
什么是质数？
遍历取模
遍历取模函数式版本
正则表达式法
开方优化
性能比较
素性测试 (Primality test)
什么是质数？
质数（Prime number，又称素数），指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。
遍历取模
判断当前整数是否为质数最常规的方法，就是让它与所有小于它的数（且大于1）取模。
const isPrime = num => { for (let i = 2; i < num; i++) if (num % i === 0) return false; return num > 1;}
const log = n =>{ console.time(n); console.log(n, isPrime(n)); console.timeEnd(n);}
[2,3,4,5,6,7,8,9,10,11,197,977,7919,51977,99991,999983,999987,1000000007,12345678911].map(log);
...
10 false
10: 0.025ms
11 true
11: 0.025ms
197 true
197: 0.034ms
977 true
977: 0.063ms
7919 true
7919: 0.362ms
51977 true
51977: 2.624ms
99991 true
99991: 1.359ms
999983 true
999983: 5.989ms
999987 false
999987: 0.024ms
1000000007 true
1000000007: 6007.705ms
12345678911 false
12345678911: 0.046ms
遍历取模函数式版本
可以用数组方法替代for循环。
正则表达式法
1的个数来实现监测质数的功能的。此正则表达式分成 由”|”分割两部分: /^1?$/和/^(11+?)\1+$/。(11+?)表示至少有两个1，(11+?)\1中的\1表示对前面的匹配的引用。\1+表示前面的(11+?)出现至少一次，相当于(11+?){2,}。整个式子的含义为至少出现两次(11+?)。也就是说，所匹配的数可以写成两个大于2的整数的乘积。而?通过backtrace穷举所有的可能行，从而完成匹配所有的合数。|连接，不匹配的就只能是质数了。开方优化
以上方案中，遍历取模是适用而比较广的，它能检测到质数相对较大。
质因数（素因数或质因子）在数论里是指能整除给定正整数的质数。除了1以外，两个没有其他共同质因子的正整数称为互质。
1没有质因子。 5只有1个质因子，5本身。（5是质数） 6的质因子是2和3。(6 = 2 × 3) 2、4、8、16等只有1个质因子：2。（2是质数，4 =2²，8 = 2³，如此类推） 10有2个质因子：2和5。(10 = 2 × 5)
性能比较
开方优化>>遍历取模>函数式遍历取模>正则表达式。
参考资料
A wild way to check if a number is prime using a regular expression | by Mark Sauer-Utley | ITNEXT 正则表达式检测质数 | HE Tao Demystifying The Regular Expression That Checks If A Number Is Prime – The Codeumentary
往期推荐