Which is the fastest algorithm to find prime numbers?

c++ algorithm primes
kasperasky picture kasperasky · Jan 17, 2009 · Viewed 324.3k times · Source

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

Greg Hewgill picture Greg Hewgill · Jan 17, 2009

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.

Related questions

Printing prime numbers from 1 through 100

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97. But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop …

Read More
Fastest algorithm for primality test

I need to test primality on intervals between numbers which are really big (in the range of long long), so i need some fast algorithm for checking if a number is prime or not. Please suggest your ideas.

Read More
Efficient Prime Factorization for large numbers

I've been working on a little problem where I need to compute 18-digit numbers into their respective prime factorization. Everything compiles and it runs just fine, considering that it actually works, but I am looking to reduce the run time …

Read More