Alfr3d

BlogAboutShort

如何用正则表达式判断一个数是否是质数

avatar
Alfxjx

本文展示了一种判断一个数是否是质数的奇技淫巧,采用的是正则表达式方法。

太长不看

function isPrime(n){
    return !(Array(n+1).join(1).match(/^1?$|^(11+?)\1+?$/))
}

原理解释 这个方法主要分为三步:

将待求数字转变为一元形式(unary form); 检测这个数是一还是零; 检测这个数是否是很多个 1 组成; 我们分开来慢慢说:

Array(n+1).join(1)这是将数字转化为一个长度为待求 n+1 的数组。

在 ES6 下,也可以这么写:"1".repeat(n);

接下来就是正则匹配的过程。/^1?$/匹配的是一个开头为 1,结尾也是 1 的数,数量为 1 个或者一个也没有。这就是第二步的作用。

/^(11+?)\1+$/ 这个正则匹配的是第三步,首先一个捕获组(/11+?/)匹配的是至少两个 11 为一组的情况,在 + 之后的 ? 表示这个匹配是非贪心的,要是没有这个?的话,这个捕获组就会匹配全部的字符串了。

再之后我们看一下\1+?,这会返回第一个匹配的位置,+?同样表示非贪心匹配。

总而言之,第三步是这样匹配的:当捕获组匹配到“11”时,同时会确定他的位置,接着正则表达式会匹配复数个”11”,如果匹配失败了(例如 n 是奇数的情况),那么匹配会返回之前的位置,并在括号里面加一个 1 来继续匹配,重复上面的动作。

这看起来就好像在使用多个数去整除输入的整数 n 一样。

如果匹配结果是 true,那么就说明这个数是 1)0 或 1;2)它会被整除,因此是合数,所以给返回值添加一个取反(!)。

ES6 的写法是这样的:

function isPrime(n){
    const regex = /^1+?$|^(11+?)\1+?$/
    return !("1".repeat(n).match(regex))
}

其他 相信你也能看出来,这个方法非常的蛮。是的,一般来说判断一个数是否是质数的方法是这样的:

function isPrime(n){
    const root = Math,sqrt(n)
    for(let i=0;i<=root;i+=2){
        if(n%i===0){
            return false
        }
    }
    return true
}

时间复杂度是 O(n^0.5),这个方法大概是 O(n);

此外,该方法受 String 长度的限制,大多数浏览器中,string 的最大长度小于 2.68 亿,所以不能判断诸如 1000000000000066600000000000001 是否是质数。(当然她是)

总的来说,这个方法也蛮有意思的。

原文链接

regexjavascript