求给定正数素数的最优和最常用算法

Question

当我在大学的时候，作为一个编程语言学习者，我写了一个程序来找出素数，但是我从不在意程序在速度上的表现。现在，经过很长一段时间，projecteuler.net才刚刚开始解决问题。

现在，我想知道，是否有任何最佳和最常用的算法来寻找一个给定的正数的素数，从而快速产生结果？

谢谢

Answer 1

对于非常大数目的素数测试，有一些概率方法：

http://en.wikipedia.org/wiki/Primality_test#Probabilistic_测试

最流行的原始性测试是概率检验。这些测试除了使用测试数n之外，还使用从某些样本空间随机选择的其他一些数字a；通常的随机素数检验从不将一个素数报告为复合数，但复合数可能被报告为素数。通过使用a的几个独立选择的值重复测试，可以降低错误发生的概率。

Answer 2

最快的方式将是一个查表：

此页面索引存储在此站点中的许多素数列表。我们保留的主要列表是5000个最大已知素数和选定的较小素数的列表。我们也有第一个素数的列表，但是保留这样的名单太长了是不实际的。

Answer 3

拒绝试用素数的一个非常快速的方法是使用这样一个事实，即所有素数都是6k +/- 1形式，其中k是正整数。(2及3除外)。

这意味着您只需要两个测试就可以拒绝一个数字(加上琐碎的测试)。

public static boolean checkPrime(long p)
{
   if (p==2 || p==3) return true;
   if ( (p+1) % 6 == 0 || (p-1) % 6 == 0 ) 
   {
      // p might be prime, worth checking
      return checkProbablePrime(p);
   }
   else
   {
     // p is not prime.
     return false;  
   }
} 

这是否是一种好的技术取决于投入的分配。如果您期望合成数字的百分比很高，那么这是从争用中消除它们的一种快速方法。最好消除顶部的琐碎分支(==2，==3)，但这取决于输入的上下文。如果你的目标是找到素数，那么你应该跳过这个。