A small and fast(?) prime number generator, written in C++.
To test if a number n
is prime, this algorithm checks if n
is divisible by any prime that is at most sqrt(n)
. As a further optimization, all even n
are skipped.
By the prime number theorem, the number of primes before any number n
approaches n / log(n)
. Thus, testing if n
is prime takes O(sqrt(n) / log(sqrt(n))
) = O(sqrt(n) / log(n)
) time.
This is in comparison to a more naive algorithm that checks if n
is divisble by every number before sqrt(n)
, which would take O(sqrt(n)
) time for each n
.