两种素数判定方法实现
实现一个 isPrime
方法,返回布尔值对应是否素数。
function isPrime(num) {
for (let i = 2; i < num; i++) {
if (num % i === 0) {
return false
}
}
return true
}
这是最简单有效的方法了,时间复杂度 O(n)
。最近在群里看到一种用正则来寻找素数的方法,挺耐人寻味。
function isPrime(num) {
return !/^1?$|^(11+?)\1+$/.test(Array(num+1).join('1'))
}
分析下代码,Array(num+1).join('1')
返回一个有 num 个 1 的字符串。然后用 /^1?$|^(11+?)\1+$/
去匹配该字符串。前面部分的 /^1?$/
用来匹配到 0个 或 1个 字符,对应数字 0 和 1。后面部分
/^(11+?)\1+$/
的意思是,能否匹配 n 个 m 长度的字符。这也正好对应了合数可以表示为两个整数的乘积,很巧妙。
但是我们来测试一下二者的运算速度。
function isPrime(num) {
var justNow = new Date().getTime()
for (let i = 2; i < num; i++) {
if (num % i === 0) {
console.log(new Date().getTime() - justNow)
return false
}
}
console.log(new Date().getTime() - justNow)
return true
}
isPrime(511111)
// 4
// true
function isPrime(num) {
var justNow = new Date().getTime()
var result = !/^1?$|^(11+?)\1+$/.test(Array(num+1).join('1'))
console.log(new Date().getTime() - justNow)
return result
}
isPrime(511111)
// 42912
// true
这里时间相差了 10k+ 倍。