Sieve of Eratosthenes is an algorithm for finding all the prime numbers in a segment [1;n] using O(nloglogn) operations.
The algorithm is very simple: at the beginning we write down all numbers between 2 and n.
We mark all proper multiples of 2 (since 2 is the smallest prime number) as composite. A proper multiple of a number x, is a number greater than x and divisible by x. Then we find the next number that hasn't been marked as composite, in this case it is 3.
Which means 3 is prime, and we mark all proper multiples of 3 as composite. The next unmarked number is 5, which is the next prime number, and we mark all proper multiples of it. And we continue this procedure until we processed all numbers in the row.
In the following image you can see a visualization of the algorithm for computing all prime numbers in the range [1;16].
It can be seen, that quite often we mark numbers as composite multiple times.
Let's prove that algorithm's running time is O(nloglogn). The algorithm will perform np operations for every prime p≤n the inner loop. Hence, we need to evaluate the next expression:
∑p≤n,p primenp=n⋅∑p≤n,p prime1p.
Let's recall two known facts.
The number of prime numbers less than or equal to n is approximately nlnn.
The k-th prime number approximately equals klnk (that follows immediately from the previous fact).
Thus we can write down the sum in the following way:
∑p≤n,p prime1p≈12+∑k=2nlnn1klnk.
Here we extracted the first prime number 2 from the sum, because k=1 in approximation klnk is 0 and causes a division by zero.
Now, let's evaluate this sum using the integral of a same function over k from 2 to nlnn (we can make such approximation because, in fact, the sum is related to the integral as its approximation using the rectangle method):
∑k=2nlnn1klnk≈∫nlnn21klnkdk.
The antiderivative for the integrand is lnlnk. Using a substitution and removing terms of lower order, we'll get the result:
∫nlnn21klnkdk=lnlnnlnn−lnln2=ln(lnn−lnlnn)−lnln2≈lnlnn.
Now, returning to the original sum, we'll get its approximate evaluation:
∑p≤n,p is primenp≈nlnlnn+o(n).
You can find a more strict proof (that gives more precise evaluation which is accurate within constant multipliers) in the book authored by Hardy & Wright "An Introduction to the Theory of Numbers"
int n;
vector is_prime(n+1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i++) {
if (is_prime[i] && (long long)i * i <= n) {
for (int j = i * i; j <= n; j += i)
is_prime[j] = false;
}
}