algorithm - 如何找到给定数量的素数？

Question

我需要从 2 开始按升序查找一定数量的素数。我有一个工作算法，它将数字限制作为参数 - 它找到所有小于限制的素数。

例如 - 对于参数 20 它将返回 2,3,5,7,11,13,17,19，但我需要输入 5 并得到 2,3,5,7,11。什么是最好的方法？我正在使用 Eratosthenes 筛法，没有办法限制数字删除部分，因为我不知道第 195 个素数有多大，因此我不知道是否应该删除所有 2 的倍数1568或1268426。希望问题清楚，谢谢帮助

Answer 1

有几种方法可以做你想做的事。

素数定理说小于n的素数的个数渐近等于n/log(n)。您可以添加一个小缓冲区，然后执行埃拉托色尼筛法，并丢弃超出限制的任何素数。

有一些公式可以在不列出素数的情况下计算小于 n 的素数的确切数量，而不是近似值。您可以使用其中一个公式找到第 n 个素数，然后使用 Sieve 生成​​素数列表。如果您想采用这种方法，请在 Google 上搜索“Legendre sum”和“Lehmer 公式”。

您可以使用分段的埃拉托色尼筛法。筛选到一些方便的限制。如果你得到了答案，就停下来。否则，选择下一段，然后是下一段，依此类推，直到找到所需的素数个数。

有一种生成无限素数列表的非常聪明的方法，它用优先级队列代替埃拉托色尼筛法的位数组。谷歌搜索 Melissa O'Neill 的论文 The Genuine Sieve of Eratosthenes。

您可以查看所有这些算法的完整解释和实现 here .

对了，第195个素数是1187，小于1568的素数有247个，小于1268426的素数有97790个。