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)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 notates if an element is deleted.

1
2
3
4
5
6
7
8
9
10
constexpr int N; // the given number N is defined elseware
vector<int> primes;

vector<bool> sieve(N+1, true);
for (int i = 2; i <= N; ++i) if (sieve[i]) { // start with 2
primes.push_back(i); // gathered a prime number
for (int j = i; j <= N; j += i) {
sieve[j] = false;
}
}

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

The outer for-loop execute NN times obviously. So it's Θ(N)\Theta (N). For every prime number found, the inner for-loop execute Np\frac{N}{p} times. Thus the statement sieve[j] = false execute NpN1piN\sum_{p \leq N}\dfrac{1}{p_i} times in total where pip_i is the iith prime number. Then, applying Mertens' second theorem: limn(pn1pilnlnnM)=0 \lim_{n \to \infty} \left( \sum_{p \leq n}\frac{1}{p_i} - \ln \ln n - M\right) = 0 where M0.2615M \approx 0.2615. thus we can say NiN1pi=Θ(NlnlnN)N \sum_{i \leq N}\dfrac{1}{p_i} = \Theta (N \ln \ln N) and it is the time complexity of sieve.