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.

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.

1. 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.

2. 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}.

3. Legendre’s conjecture: There is always a prime between numbers n2 and (n + 1)2, where n is any positive integer. For example 5 and 7 between 22 and 32.

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.

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.

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;
}

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.

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