这个奇怪的JavaScript函数如何用于primality检查工作？

Question

这是功能:

var isPrime = function(x) {
    return (!(/^,?$|^(,,+?)\1+$/.test(Array(++x))));
};

它适用于小数字,但是当数字很大时,会抛出一个异常,表示数组长度无效.我无法理解这里发生了什么.RegEx测试的作用是什么？为什么这段代码有效？

Answer 1

Array(++x)首先产生一串x逗号.

正则表达式现在:

^,?$         // Match 1 , or none
|            // or ...
^(,,+?)\1+$  // A specific number of commas, elaboration below:

逗号的数量至少等于2个逗号,然后重复直到结尾.它试图做的是:

它首先尝试匹配2个逗号(,+?匹配至少1个,懒惰),并使用它来匹配2的所有倍数,除了2本身,因为反向引用\1是强制性的.所有2的倍数因为^(,,)\1+$匹配偶数,.

旁注:\1是一个反向引用,并且将匹配第一个捕获组匹配的内容,在此初始情况下(,,).所以在第一阶段,\1将匹配2个逗号.

如果匹配,则表示存在偶数个逗号且该数字不是素数.
如果以上不匹配,则匹配3个逗号,并使用它来匹配3的所有倍数,再次,除了3本身.所有3的倍数因为^(,,,)\1+$匹配3 的,倍数.

旁注:这一次,\1将匹配,(,,,)因为现在已经在捕获组中.所以在第二阶段,\1将匹配3个逗号.

如果匹配,则表示有多个逗号可以被3整除,因此不是素数.

等等.你可以看到模式？

所以正则表达式实际上会检查从2开始的所有数字,直到(,,+?)长度与Array(++x)返回的数字相等.当然,对于大数字,您可能会遇到不同类型的错误:

传递给函数的数字对于正则表达式来说太大了,你会得到"堆栈溢出,因为正如试图找到匹配的正则表达式试图在内存中保留太多东西",正如Floris在评论中提到的那样(发生这种情况)在node.js上的下一个错误之前);
形成的数组Array(++x)有太多JS不支持的元素.

因此,如果正则表达式匹配,则它不是素数.这也是你!在开始时否定正则表达式测试结果的原因.

Answer 2

Array(++x).toString()是一串x逗号.

这检查它是由以下两者组成的:

所以它检查x是否

这就是不是素数的定义.

更详细的解释:

请注意,没有什么魔力:它很昂贵,因为它会要求引擎测试所有可能的大小,(,,+?)直到找到一个.