关于不可知的语言：无穷素数的计数方法

好吧，所以也许我不应该将这个问题缩得太多...我已经看到了找到前10000个素数的最有效方法的文章。 我正在寻找所有可能的方式。 目标是建立一站式的原始测试。 我们欢迎人们发现质数的所有测试。

所以：

• 寻找素数的所有不同方式是什么？

某些素数测试仅适用于特定数字，例如，卢卡斯-莱默(Lucas–Lehmer)检验仅适用于梅森数字。

大多数用于大数的素数测试只能告诉您某个数字"可能是素数"(或者，如果该数字未通过测试，则肯定不是素数)。通常，您可以继续执行算法，直到极有可能是质数。

请查看此页面，尤其是其"另请参见"部分。

我认为，Miller-Rabin测试是最好的测试之一。在标准格式中，它为您提供了可能的质数-尽管已经表明，如果将测试应用于3.4 * 10 ^ 14以下的数字，并且可以通过每个参数2、3、5、7、11、13的测试和17，绝对是黄金。

AKS测试是第一个确定性，经过验证的通用多项式时间测试。但是，据我所知，除非输入非常大，否则它的最佳实现却比其他测试慢。

罗格斯大学的一名研究生最近发现了一个产生素数的递归关系。其连续数的差将生成素数或1。

它产生了很多需要过滤掉的废话。 Benoit Cloitre也具有这种重复发生，可以执行类似的任务：

则连续数的比率减去1 [b(n)/ b(n-1)-1]为质数。您可以在递归中阅读所有这些内容的完整说明。

对于筛子，您可以使用轮子而不是每次添加一个轮子来做得更好，请查看"改进的增量质数筛子"。这是一个轮子的例子。让我们看一下要忽略的数字2和5。他们的轮子是[2,4,2,2]。

@akdom对我的问题：

循环可以很好地满足我之前的建议，您无需进行任何计算即可确定数字是否为偶数。在循环中，只需跳过每个偶数，如下所示：

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

Take a list of 2 to the square root of the integer.

Loop through the list, taking the remainder of the integer / current number

If the remainder is zero for any number in the list, then the integer is not prime.

If the remainder was non-zero for all numbers in the list, then the integer is prime.

它使用的内存比Eratosthenes筛子要少得多，并且对于单个数字来说通常更快。

---

Eratosthenes筛子是一种不错的算法：

Take the list of positive integers 2 to any given Ceiling.

Take the next item in the list (2 in the first iteration) and remove all multiples of it (beyond the first) from the list.

Repeat step two until you reach the given Ceiling.

Your list is now composed purely of primes.

此算法有功能上的限制，因为它会交换内存速度。当生成非常大的素数列表时，所需的存储容量会飞速增长。

---

@theprise

如果我要使用递增循环而不是实例化列表(存在大量数字的内存问题...)，那么在没有构建列表的情况下，这样做的好方法是什么？

对于给定的整数(X％3)进行除数检查似乎并不比对普通数(N％X)进行检查便宜。

---

在使用从2到整数根的列表的算法中，可以通过仅测试2之后的奇数来提高性能。也就是说，列表仅需要包含2以及从3到整数平方根的所有奇数。 。这样可以将循环次数减少一半，而不会增加任何复杂性。

---

如果您想找到一种生成质数的方法，则在上一个问题中已经介绍了此方法。

---