The most efficient way to find every prime number no more than a specific number N is called sieve of Eratosthenes, or sieve for short. it has almost time complexity which can be obviously seen in the following introduction.
The basic idea of sieve is trival: list every number in the interval (1, N], repeatly delete every multiple of it's first element until there is no element in the list. here is the C++ code using a vector to save prime numbers and a vector
constexpr int N; // the given number N is defined elseware
Now prove the result is exactly what we want. For element which is the first element in the list, the cyclic invariant guaranteed thus is a prime number. Assume a prime number not belongs to the result, since every undeleted element in (1, N] is iterated, must be deleted cause of some number . the existence of contradict with the assumption thus there is no such number .
The outer for-loop execute times obviously. So it's . For every prime number found, the inner for-loop execute times. Thus the statement
sieve[j] = false execute times in total where is the th prime number. Then, applying Mertens' second theorem: where . thus we can say and it is the time complexity of sieve.