方法来计算的无限素数

好吧中，所以也许我不应该SOOO多缩水这个问题......我看到的the most efficient way to find the first 10000 primes职。我在寻找所有可能的方式。目标是为素质测试提供一站式服务。任何人都知道寻找素数的测试是受欢迎的。方法来计算的无限素数

所以：

什么都找到素数的不同方式？

来源

2008-08-10 akdom

请注意，您可以计算n以下的素数而无需计算所有这些素数：https：//en.wikipedia.org/wiki/Prime-counting_function#Algorithms_for_evaluating_.CF.80.28x.29 – 2015-07-13 01:20:53

The Sieve of Eratosthenes是一个体面的算法：

取正整数的列表2至任何给定的天花板。

采取的下一个项目中（在第一次迭代2）列表，从列表中删除它的所有倍数（超出第一）。

重复第二步，直到达到给定的上限。

你的列表现在由纯粹的素数。

该算法存在功能限制，因为它交换内存的速度。当生成非常大的素数列表时，内存容量需要突然增加。

来源

2008-08-10 18:17:41 akdom

缺少关键细节在这里：你如何找到，以及如何“移除”倍数。如果你找到它们的方式是正确的，也就是从素数的一个数字开始计数，那么**根本不能移除它们，因为那样你就不能计数**。 SoE指向*标记*倍数，使用*值*作为*地址*，没有任何值的比较（因此避免了复杂性中额外的“log n”因子）。这与使整数排序比比较排序更接近。如果你真的*删除*他们，你放弃这个优势。 – 2012-09-20 03:41:58

对于一个给定的整数，最快的素性检查我所知道的是：

取2的列表的整数平方根。

遍历列表，采取的其余整数/目前一些

如果余数为任何数量的列表中的零，那么整数不是素数。

如果余数为非零列表中的所有号码，那么整数是素数。

它采用显著较少的内存比The Sieve of Eratosthenes和普遍较快个人号码是。使用2列表中的整数根

来源

2008-08-10 18:26:43 akdom

在你的算法，可以通过只有2个即经过测试奇数提高性能，您只列出需要包含2和所有的奇数3的平方整数的根。这会减少循环次数，而不会引入更多的复杂性。

来源

2008-08-10 19:58:38 goric

@theprise

如果我想用一个递增的循环，而不是一个实例列表（问题内存庞大的数字...），这将是这样做没有建立名单的好办法？

对给定的整数（X％3）进行可分性检查似乎并不像检查正常数字（N％X）那样便宜。

来源

2008-08-10 20:18:27 akdom

-1

如果你想找到生成素数的方法，这已经在previous question中涵盖。

来源

2008-08-10 22:47:08 GateKiller

@ akdom的问题，对我说：

环流式将正常工作我以前的建议，你不需要做任何的计算，以确定是否一个数是偶数;在循环，直接跳过每个偶数，如下图所示：

//Assuming theInteger is the number to be tested for primality. 
// Check if theInteger is divisible by 2. If not, run this loop. 
// This loop skips all even numbers. 
for(int i = 3; i < sqrt(theInteger); i + 2) 
{ 
    if(theInteger % i == 0) 
    { 
     //getting here denotes that theInteger is not prime 
     // somehow indicate that some number, i, divides it and break 
     break; 
    } 
}

来源

2008-08-11 01:42:41 goric

罗格斯研究生最近发现了一个recurrence relation that generates primes。它的连续数字的差别会产生素数或1。

a(1) = 7 
a(n) = a(n-1) + gcd(n,a(n-1)).

这使得很多废话需要过滤掉。贝努瓦Cloitre也有这种复发，做了类似的任务：

b(1) = 1 
b(n) = b(n-1) + lcm(n,b(n-1))

然后连续数的比，减一[B（N）/ B（N-1）-1]为素数。所有这些的完整说明可以在Recursivity阅读。

对于筛子，您可以通过使用轮子而不是每次添加一个来获得更好的效果，请查看Improved Incremental Prime Number Sieves。这是一个车轮的例子。让我们看看数字，2和5来忽略。他们的轮子是[2,4,2,2]。

来源

2008-08-11 02:31:36 nlucaroni

某些主要测试仅适用于某些数字，例如，Lucas–Lehmer测试仅适用于梅森数字。

用于大数字的大多数主要测试只能告诉您某个数字是“可能为素数”（或者，如果数字未通过测试，肯定是而不是素数）。通常情况下，您可以继续使用算法，直到数字出现质数的概率非常高。

看看this page，特别是它的“另请参见”部分。

Miller-Rabin test是，我认为，最好的测试之一。在它的标准形式中，它给出了可能的素数 - 尽管已经表明，如果将测试应用于3.4 * 10^14以下的数字，并且它通过了每个参数2,3,5,7,11,13的测试和17，它是，绝对是总理。

AKS test是第一个确定性的，证实的，通用的多项式时间测试。然而，据我所知，最好的实现结果是比其他测试慢，除非输入是可笑的大。

来源

2008-10-28 06:30:04 Artelius

方法来计算的无限素数

回答

相关问题