Prime Numbers and Sieve of Eratosthenes
A prime number is an integer n > 1 which is only divisible by 1 and n(itself). For example, 2, 3, 5 are prime numbers, but 6, 8, 9 are not prime numbers.
Every integer n > 1 can be uniquely expressed as the product of prime numbers. For example 8 = 2 * 2 * 2.
Some facts about prime numbers:
 Except 2, all prime numbers are odd.
 All prime numbers greater than 3 can be written in the form 6k ± 1.
 1 is not a prime number.
A perfect number is a number n if n is equal to the sum of its factors between 1 and n – 1. For example 28 is a perfect number because 28 = 1 + 2 + 4 + 7 + 14.
Conjectures

Goldbach’s conjecture: Each even integer n > 2 can be represented as a sum n = a + b such that both a and b are prime numbers. For example 12 = 5 + 7.

Twin prime conjecture: There is an infinite number of pairs of the form {p, p + 2}, where both p and p + 2 are prime numbers. For example {5, 7}, {11, 13}.

Legendre’s conjecture: There is always a prime between numbers n^{2} and (n + 1)^{2}, where n is any positive integer. For example 5 and 7 between 2^{2} and 3^{2}.
Basic Algorithm
If a number n > 1 is not a prime number then it has a factor between 2 and floor (√n). For example 27 = 3*9 and √27 = 5.196 then 27 has a factor between 2 and 5 which is 3. So to test if a number is prime number we have to iterate to √n in a loop.
Here is a function is_prime
which checks if the given number is prime.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool is_prime(int n)
{
if (n < 2)
{
return false;
}
for (int i = 2; i*i <= n; ++i)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
Here is the function prime_factorization
which returns an array of prime factors of the number.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
std::vector<int> prime_factorization(int n)
{
std::vector<int> factors;
for (int i = 2; i*i <= n; ++i)
{
while (n % i == 0)
{
factors.push_back(i);
n = n / i;
}
}
if (n > 1)
{
factors.push_back(n);
}
return factors;
}
Sieve of Eratosthenes
It is an efficient algorithm to find prime numbers upto a limit (say 10,000,000).
In this algorithm, first we mark all the multiples of 2 upto n, then all the multiples of 3, then 5 and so on. In the end we have all the prime numbers upto n.
For example, to find prime numbers less tha or equal to 20.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Now we mark all the multiples of 2 except 2 with red.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Now we mark all the multiples of 3 except 3 with red.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
The remaining integers in black are prime numbers less than 20.
Here is the function sieve_of_erastosthenes
which returns an array whose index can tell us the prime numbers less than or equal to n.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
std::vector<bool> sieve_of_erastosthenes(int n)
{
std::vector<bool> is_prime(n+1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; ++i)
{
if (is_prime[i])
{
for (int j = i*i; j <= n; j += i)
{
is_prime[j] = false;
}
}
}
return is_prime;
}
Reference  Competitive Programmer’s Handbook, Antti Laaksonen
Get this post in pdf  Prime Numbers and Sieve of Eratosthenes