这个奇怪的JavaScript原数检查函数是如何工作的?

How does this weird JavaScript function for primality check work?

本文关键字：何工作 工作 检查 JavaScript 函数      更新时间：2023-09-26

这是函数:

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

它适用于较小的数字，但是当数字很大时，抛出一个异常说数组长度无效。我不明白这是怎么回事。RegEx测试做什么?为什么这段代码可以工作?

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整除，因此不是素数。

以此类推。你能看到这个模式吗?

所以regex实际上会检查从2到(,,+?)的长度等于Array(++x)返回的所有数字。当然，对于较大的数字，您可能会得到不同类型的错误:

  1. 你传递给函数的数字对于正则表达式来说太大了，你会得到"一个堆栈溢出，因为正则表达式试图在内存中保留太多的东西，因为它试图找到一个匹配"，正如Floris在评论中提到的(这发生在node.js上的下一个错误之前);

  2. Array(++x)组成的数组元素太多，JS不支持

如果正则表达式匹配，它就不是质数。这也是为什么您在开始时使用!来否定regex测试的结果。

Array(++x).toString()是由x逗号组成的字符串。

检查它是否由以下两种元素组成:

  • ,?: 0或1逗号
  • (,,+?)'1+:重复多个逗号至少2

检查x是否为

  • 0或1
  • 或大于或等于2
    • 的数字的倍数

这就是非素数的定义

更详细的说明:

  • /^A|B$: A或B，从开始到结束
  • ,?:逗号，可选(so, 0或1)
  • (,,+?): 1个或多个逗号，但不贪婪
  • '1+第一组重复一次或多次

请注意，这里没有魔法:它会要求引擎测试所有可能的(,,+?)大小，直到找到一个。

相关文章：