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 $O(N)$ 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

1 | constexpr int N; // the given number N is defined elseware |

Now **prove** the result is exactly what we want. For element $n$ which is the first element in the list, the cyclic invariant guaranteed $\left\{k\ |\ n|k\right\} \land (1, N] = \emptyset$ thus $n$ is a prime number. Assume a prime number $p \in (1, N]$ not belongs to the result, since every undeleted element in (1, N] is iterated, $p$ must be deleted cause of some number $k \left(p|k\right)$. the existence of $k$ contradict with the assumption thus there is no such number $p$.

The outer for-loop execute $N$ times obviously. So it's $\Theta (N)$. For every prime number found, the inner for-loop execute $\frac{N}{p}$ times. Thus the statement `sieve[j] = false`

execute $N\sum_{p \leq N}\dfrac{1}{p_i}$ times in total where $p_i$ is the $i$th prime number. Then, applying Mertens' second theorem: $\lim_{n \to \infty} \left( \sum_{p \leq n}\frac{1}{p_i} - \ln \ln n - M\right) = 0$ where $M \approx 0.2615$. thus we can say $N \sum_{i \leq N}\dfrac{1}{p_i} = \Theta (N \ln \ln N)$ and it is the time complexity of *sieve*.