如何找到一些素数？ [英] How to find a number of prime numbers?

问题描述

我需要找到一定数量的素数。我有一个工作的算法，这需要一些限制作为参数 - 它发现小于限值的所有素数。

I need to find a certain amount of prime numbers. I have a working algorithm which takes a number-limit as a parameter - it finds all primes that are less than the limit.

例如 - 对于参数 20 它会返回 2,3,5,7,11,13,17,19 ，但我需要输入 5 并获得 2,3,5,7,11 。什么是最好的方法是什么？我使用埃拉托色尼的筛子，也没有办法限制的数量，删除的部分，因为我不知道有多大的第195素数是和因此，我不知道我是否应该删除的2倍数达1568或1268426.我希望这个问题是清楚的，感谢您的帮助

For example - for param 20 it would return 2,3,5,7,11,13,17,19, but I need to input 5 and get 2,3,5,7,11. What is the best way? I am using the Sieve of Eratosthenes and there is no way to limit the number-deleting part, since I don't know how big the 195th prime number is and I therefore don't know if I should delete all multiples of 2 up to 1568 or 1268426. I hope the question is clear, thanks for help

推荐答案

有几种方法可以做到你想要什么。

There are several ways to do what you want.

素数定理说，素数少于数量的 N 的渐近相等的 N 的/日志（ N 的）。你可以添加一个小缓冲区，然后做埃拉托色尼的筛，并抛出了超过你的极限任何素数。

The prime number theorem says that the number of primes less than n is asymptotically equal to n/log(n). You could add a small buffer, then do the Sieve of Eratosthenes, and throw out any primes beyond your limit.

而不是一个近似值，也有计算素数小于的 N 的确切数量，而不列出的素数的公式。可以使用这些公式中的一个来发现的 N 的第素数，然后使用筛，使素数的列表。谷歌的勒让德之和莱默的公式，如果你想要采取这种方式。

Rather than an approximation, there are formulas that compute the exact number of primes less than n without listing the primes. You could use one of those formulas to find the n th prime, then use a Sieve to make the list of primes. Google for "Legendre sum" and "Lehmer's formula" if you want to take this approach.

您可以使用埃拉托色尼的分割筛。筛了一些方便的限制。如果你已经有了答案，停止。否则，选择下一个片段，然后下一个，依此类推，直到你找到你想要的素数的数量。

You could use a segmented Sieve of Eratosthenes. Sieve up to some convenient limit. If you've got the answer, stop. Otherwise, pick the next segment, and then the next, and so on until you've found the number of primes that you want.

有生成素，它取代了位阵列埃拉托色尼的筛与优先级队列的无限列表的一个非常聪明的方法。谷歌的梅丽莎奥尼尔的文件的埃拉托色尼的真正筛的。

There is a very clever method of generating an infinite list of primes that replaces the bit-array of the Sieve of Eratosthenes with a priority queue. Google for Melissa O'Neill's paper The Genuine Sieve of Eratosthenes.

您可以看到所有这些算法这里完整的解释和实施。

You can see complete explanations and implementations of all of these algorithms here.

顺便说一下，第195素是1187.有247的素数小于1568，和97790素数小于1268426。

By the way, the 195th prime is 1187. There are 247 primes less than 1568, and 97790 primes less than 1268426.

这篇关于如何找到一些素数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！