1

我从http://www.javascripter.net/faq/numberisprime.htm看到下面的代码

leastFactor = function(n){
 if (isNaN(n) || !isFinite(n)) return NaN;  
 if (n==0) return 0;  
 if (n%1 || n*n<2) return 1;
 if (n%2==0) return 2;  
 if (n%3==0) return 3;  
 if (n%5==0) return 5;  
 var m = Math.sqrt(n);
 for (var i=7;i<=m;i+=30) {
  if (n%i==0)      return i;
  if (n%(i+4)==0)  return i+4;
  if (n%(i+6)==0)  return i+6;
  if (n%(i+10)==0) return i+10;
  if (n%(i+12)==0) return i+12;
  if (n%(i+16)==0) return i+16;
  if (n%(i+22)==0) return i+22;
  if (n%(i+24)==0) return i+24;
 }
 return n;
}

这是否意味着质数在数字 7 之后每 30 次总是具有相同的模式？

这是否意味着从 7 开始，当你加 30 时，那个数字的结果是素数，那个数字 +4 是素数，那个数字 +6 总是素数，依此类推，直到 +24，之间就不会再有素数了他们？

4

3 回答 3

3

不，但是此代码有效，因为它只是检查所有值（有点）。你知道，如果一个数字是偶数，它是 2 的倍数，而不是质数。同样，如果它最右边的数字是 5，你就知道它可以被 5 整除而不是素数。使用许多这样的规则，我们可以消除检查满足这些参数之一的许多不同值。

因此，脚本检查 2，发现 2 不是输入的倍数，并且知道它永远不需要再次检查偶数，依此类推。

for 循环不仅仅生成素数。它可以生成 187，这不是素数，但在实践中，它永远不会，因为一旦函数检查 11，它就会返回。

于 2013-01-22T02:58:38.213 回答
2

它基本上只是避免重新检查不可能的除数，因为它们是已经检查过的 2,3 或 5 的倍数。这是仍然可能除数的重复模式，因为 2,3 和 5 的乘积是 30。

根本没有发现质数遵循非常可预测的模式。

于 2013-01-22T03:01:56.360 回答
1

该代码所做的是高度优化的——它本质上与“3 是否均匀划分为 n？4是否均分n？5 是否均分为 n？但它使用重要的知识，例如“在 2 之后，没有偶数是素数”来跳过检查所有偶数因子（注意它会做 7 + 偶数、37 + 偶数、67 + 偶数等等 - 所以从来没有偶数）。同样，它会跳过每六个因数，因为它是 3 的倍数。

于 2013-01-22T02:48:39.930 回答