Primality

Primality

This is one of the most important concepts that you'll encounter in the world of competitive programming.

A number is said to be prime if it's divisible only by 1 and itself.

For example, 2,3 and 5 are some prime numbers. We'll now look into ways to determine whether a number is prime or not.

One of the most naive algorithms to find out if a number n is prime of not would be to run a loop from 2 to n-1, checking if any number divides the number. If any number does divide n, it's a composite number. Else it's a prime. A simple implementation in C++ would be,

bool isPrime(int x)
{
    for(int i=2;i<x;i++)
    {
        if(x%i == 0)
            return false;
    }
    return true;
}

But there are ways to make this faster. This loop doesn't need to run until n-1. We can derive that there will be no factor greater than n/2(excluding itself). Hence the loop can run until n/2 and still give us the right answer.

For example, the factors of 10 are, 1 2 3 5 10

We can see that the largest factor excluding 10 is 5. The implementation in C++ would look something like,

bool isPrime(int x)
{
    for(int i=2;i<x/2;i++)
    {
        if(x%i == 0)
            return false;
    }
    return true;
}

We can still make this faster. Notice that both the above implementations still visit all the possible proper factors. But to test whether a number is prime, we don't need to check for all possible factors. Consider two proper factors a and b of a number n, such that,

a*b = n

We can prove by contradiction that one of them will be lesser than or equal to sqrt(n).
Using this theorem, we can reduce the loop even further to check until sqrt(n) for any possible divisors. The implementation would be,

bool isPrime(int x)
{
    for(int i=2; i <= sqrt(x); i++)
    {
        if(x%i == 0)
            return false;
    }
    return true;
}

Notice that in this implementation, we hit only half the number of proper divisors.
There are many more algorithms for primality test like Fermat's little theorem, Miller-Rabin test, Solovay-Strassen. But we will not look into these just yet.

Sieve of Eratosthenes

Sieve of Eratosthenes is a very simple algorithm for finding all prime numbers up to a given limit.

In this algorithm, we start from the number 2 and keep marking the composites which are the multiples of a prime. For example, if we were trying to find the primes below 11. Let the flag array be initialized to zero. The flag array signifies the compositeness of each number. It is set to 1 if it is a composite number, otherwise zero.

Iteration	0	1	2	3	4	5	6	7	8	9	10	Discovering
1	1	1	0	0	1	0	1	0	1	0	1	2
2	1	1	0	0	1	0	1	0	1	1	1	3
3	1	1	0	0	1	0	1	0	1	1	1	4
4	1	1	0	0	1	0	1	0	1	1	1	5
5	1	1	0	0	1	0	1	0	1	1	1	6
6	1	1	0	0	1	0	1	0	1	1	1	7
7	1	1	0	0	1	0	1	0	1	1	1	8
8	1	1	0	0	1	0	1	0	1	1	1	9
9	1	1	0	0	1	0	1	0	1	1	1	10

As you can notice that after iteration 1, all numbers which are the multiples of 2 have been set to 1, implying that they are composite numbers. When we move to iteration 2, all multiples of 3 have been marked composite. Notice that we do not change the mark of 2 and 3, since they weren't multiples of any smaller number, thus implying that they are primes. Once all the numbers have been visited once, we loop through the flag array and filter out the numbers with flag value set to 0. This gives us all the primes in the range. For example, in this case, the primes are,

2 3 5 7

The following animation shows the marking for finding the primes within 121.

Here's a simple implementation for sieve in C++.

//Finding all primes within the range [1,n)
void sieve(int n)
{
    bool flag[n] = {0};
    flag[0] = flag[1] = 1;              //Setting 0 and 1 as composites.
    //Finding the primes.
    for(int i=2;i<n;i++)                //Running a loop from 2 to n-1.
    {
        if(flag[i]==0)                  //Found a prime.
        {
            for(int j=2*i;j<n;j+=i)     //looping through the multiples of the prime.
                flag[j] = 1;            //Setting flag to composite.
        }
    }
    //Printing the primes.
    for(int i=0;i<n;i++)
    {
        if(flag[i]==0)
            cout << i << " ";
    }
    cout << endl;
}