揭秘素数判定：高级程序员必知的秘密技巧

时间：11-08 名人轶事提交错误

大家好，如果您还对揭秘素数判定：高级程序员必知的秘密技巧不太了解，没有关系，今天就由本站为大家分享揭秘素数判定：高级程序员必知的秘密技巧的知识，包括的问题都会给大家分析到，还望可以解决大家的问题，下面我们就开始吧！

布尔checkPrime(int n) {

for (int i=2; i*i=n; i++) {

如果（n%i==0）{

返回假；

}

返回真；

}确定素数最简单的方法就是试除法，也就是上面的代码。它的原理是从2到根n，看n是否能被某个数整除。如果可以，那么n肯定不是素数，否则一定是素数。这确实是一个简单粗暴又正确的方法。唯一的问题是它太慢了。确定一个数的时间复杂度是O(n)。如果让你用这种方法来判断一个几百位数的数是否是素数，使用当今最先进的计算机可能需要n年的时间才能计算出来。

筛选法

当然，还有一种更快的批量确定算法——埃氏筛选用于素数确定。查找n内的所有素数只需要O(n log log n)时间复杂度。

在此插入图片描述

原理是这样的，设置一个marker数组，先标记所有2的倍数，然后回去发现3没有标记，那么3一定是素数，然后在marker中标记所有3的倍数大批。然后发现4已经被标记了，跳到5.直到所有的数字都被标记了，那么剩下的未标记的数字都是质数，见上图，代码如下：

int[] 符号=new int[n+1];

无效埃拉托色尼（int n）{

for (int i=2; i=n; i++) {

if (signs[i]==0) {

for (int j=i * i; j=n; j +=i) {

标志[j]=1;

}

}艾利希筛选法虽然看起来速度更快，但它也有自己的问题。首先，它只能批量使用。在判断单个n时，还需要筛选掉所有小于n的素数。其次，它还依赖存储空间来存储标签。所以它仍然不能用来确定非常大的素数。

有没有更快的方法来找到素数？自中世纪以来，许多数学家一直致力于寻找传说中的素数公式。例如，欧拉在1772年发现当n小于41时，f(n)的值都是素数。尽管后来的数学家陆续发现了可以生成更大素数的公式，但这些公式所能生成的数字仍然是相同的。这是非常有限的。到高斯时代，基本确认了简单的素数公式不存在。因此，高斯认为确定素性是一个非常困难的问题。

费马小定理

https://upload-images.jianshu.io/upload_images/1473092-749f42e9a4e60d4b.png

然而，事情总是有转机的。让我们回到1636年，著名数学家费马在一封信中写下了这样一个公式。

如果p 是素数且a 不是p 的倍数，则a^(p-1) 1(mod p)

后来证明a不是p的倍数这个条件不是必要的。这个定理的含义是，只要p是素数，那么就永远等于1。这就是著名的费马小定理。也许您已经想知道是否可以使用这个定理来确定素数。确实，费马小定理反过来也几乎是成立的。如果一个数p可以使得a^(p-1)==1 (mod p)，则p有很大概率是素数。 010- 59000 公共课PrimeNumCheck {

公共静态布尔检查（长a，长p）{

长res=fastMod(a, p-1, p);

返回res==1；

}

公共静态长fastMod（长x，长n，长m）{

如果（n==1）{

返回x%m；

}

长tmp=fastMod(x, n1, m);

如果（n2==0）{

返回(tmp * tmp) % m;

} 别的{

返回(tmp * tmp * x) % m;

}

公共静态无效主（字符串[] args）{

System.out.println(检查(2, 7));

}

}利用上面的Java代码，可以快速、概率性地判断一个数是否是素数（判断结果并不是100%准确），这也取决于上面代码中a的选择。上面使用了快速幂算法，可以将一个数的n次方取模的时间复杂度降低到O(logn)。我们似乎能够将确定素数的时间复杂度从O(n) 降低到O(logn)。这是一个质的飞跃，从几乎不可计算到可计算。这为大素数的应用铺平了道路。

但不用担心，它有一些小缺陷。我刚才说了费马小定理的逆向几乎成立，而且我一直在强调注意这里是几乎成立。这几个字。因为某些和n也可以使为真，所以的合数称为基于a的伪素数。例如，基于2的前几个伪素数是341、561、645……但是，这样的伪素数很少。事实上，如果几乎是一个1024位的数字，伪素数的概率小于1/10^41。这个概率有多低？例如，你能根据2随机找到一个512位伪素数的概率比你赢得五百万大奖的概率要小。所以你要随机寻找一个素数，基于2 的费马小定理就足够了。

当然，如果你坚持追求更高的精度，还是可以优化的。毕竟基于2的伪素数不一定是基于其他a的伪素数，所以我们对于一个512位的数，其中基于2的伪素数不到1/10^20但是历史告诉我们，凡事总有惊喜。一些合数可以使费马定理对于任何a 成立。这些数字称为卡迈克尔数。前几个卡迈克尔数是561、1105、1729……关于卡迈克尔数还有另一个故事。

小结

费马小定理的概率解为我们提供了一种解决问题的新方法，就像使用布隆过滤器一样。它们并不是100%准确，但在精度可控的情况下可以使用。以获得更有效的解决方案。可以多换几个不同的a来进一步提升上述代码的准确性。我觉得像费马定理这样神奇的数学定理就是上帝在创造万物时埋藏的关于数字的小彩蛋，而且我也坚信这样的小彩蛋还有很多。也许有一天我们可以发现它。上帝在圆周率里藏了一个多么大的玩笑啊！