Which is the fastest algorithm to find prime numbers?

Question

Which is the fastest algorithm to find out prime numbers using C++? I have used sieve's algorithm but I still want it to be faster!

Answer 1

A very fast implementation of the Sieve of Atkin is Dan Bernstein's primegen. This sieve is more efficient than the Sieve of Eratosthenes. His page has some benchmark information.

Answer 2

If it has to be really fast you can include a list of primes:
http://www.bigprimes.net/archive/prime.php

The sieve of Atkin is faster than the sieve of Eratosthenes:

If you just have to know if a certain number is a prime number, there are various prime tests listed on wikipedia. They are probably the fastest method to determine if large numbers are primes, especially because they can tell you if a number is not a prime.

Answer 3

You can look here: High Speed Prime Numbers Calculation - really fast algorithm

Answer 4

Is your problem to decide whether a particular number is prime? Then you need a primality test (easy). Or do you need all primes up to a given number? In that case prime sieves are good (easy, but require memory). Or do you need the prime factors of a number? This would require factorization (difficult for large numbers if you really want the most efficient methods). How large are the numbers you are looking at? 16 bits? 32 bits? bigger?

One clever and efficient way is to pre-compute tables of primes and keep them in a file using a bit-level encoding. The file is considered one long bit vector whereas bit n represents integer n. If n is prime, its bit is set to one and to zero otherwise. Lookup is very fast (you compute the byte offset and a bit mask) and does not require loading the file in memory.

Answer 5

Rabin-Miller is a standard probabilistic primality test. (you run it K times and the input number is either definitely composite, or it is probably prime with probability of error 4^-K. (a few hundred iterations and it's almost certainly telling you the truth)

There is a non-probabilistic (deterministic) variant of Rabin Miller.

The Great Internet Mersenne Prime Search (GIMPS) which has found the world's record for largest proven prime (2^43,112,609 - 1 as of August 2008), uses several algorithms, but these are primes in special forms. However the GIMPS page above does include some general deterministic primality tests. They appear to indicate that which algorithm is "fastest" depends upon the size of the number to be tested. If your number fits in 64 bits then you probably shouldn't use a method intended to work on primes of several million digits.

Answer 6

It depends on your application. There are some considerations:

• Do you need just the information whether a few numbers are prime, do you need all prime numbers up to a certain limit, or do you need (potentially) all prime numbers?
• How big are the numbers you have to deal with?

The Miller-Rabin and analogue tests are only faster than a sieve for numbers over a certain size (somewhere around a few million, I believe). Below that, using a trial division (if you just have a few numbers) or a sieve is faster.