2

Until now, I've been using sieve of Eratosthenes for generating all 'n' prime numbers.

However, I was wondering does there exist a better algorithm, or can we improve an existing one which performs better ??

Rahul Patwari
  • 75
  • 2
  • 7
  • To find the Nth prime number, you need to check for (N-1) smaller prime numbers. To do that a sieve is best. – rossum Jun 24 '17 at 09:27
  • 1
    @rossum, this is not true. It is possible to find the Nth prime number without finding the previous primes. – DanaJ Jun 24 '17 at 16:19
  • Exactly my thoughts. However, there exists one more- sieve of Sundaram, which is little better. But, I want to know another efficient algo – Rahul Patwari Jun 24 '17 at 16:23
  • 2
    For generating many primes, a sieve is best. In practice, the segmented sieve of Eratosthenes is fastest (including Atkin, Sundaram, and monolithic SoE). But for just the nth prime we don't need to generate them all. – DanaJ Jun 24 '17 at 18:05
  • cf. https://stackoverflow.com/questions/9625663/calculating-and-printing-the-nth-prime-number/9704912#9704912 (search for "The fast way"). – Will Ness Jun 25 '17 at 18:05

1 Answers1

3

For sufficiently large N (e.g. more than a million or so), the best algorithm is to use an approximation (e.g. Logarithmic Integral or Riemann's R function), then use a fast prime count method such as LMO, then sieve the small remainder. This is many orders of magnitude faster than sieving.

See https://math.stackexchange.com/questions/507178/most-efficient-algorithm-for-nth-prime-deterministic-and-probabilistic

There are at least two open source implementations.

The latter has progressed past the first, and is also multithreaded.

Add: Will Ness has also pointed out a nice post from Daniel Fischer that provides a walkthrough of different ways to solve this: Calculating and printing the nth prime number

DanaJ
  • 724
  • 6
  • 9