两种素数判定方法实现

实现一个 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+ 倍。