Basic Mathematics

The field of Computer Science is built on the field of Mathematics. All the algorithms that we learn are derived from a mathematical point of view. A majority of the Competitive Coding problems that you'll encounter will have some mathematical logic or trick. Most of the times, math helps us solve the question within the necessary time constraints. In this tutorial, we'll be looking into some of the most common mathematical concepts in competitive coding.

Greatest Common Divisor and Least Common Multiple

The GCD (Greatest Common Divisor) of two numbers is defined as the largest integers that divides both the numbers. For example, 2 is the GCD of 4 and 6. From this concept, follows something called co-primes. Two numbers are said to be co-primes if their GCD is 1. For example, 3 and 5 are co-primes because their GCD is 1.

Coming to LCM (Least Common Multiple), it is defined as the smallest integer that is divisible by both the numbers. For example, 10 is the LCM of 2 and 5.

Given any two numbers a and b,

Euclid's algorithm

This is one of the most famous algorithms for computing gcd of two numbers. Consider two numbers a and b. The procedure of the Euclid's algorithm can be broken down into a sequece of equations,

If a is smaller than b, the first step of the algorithm swaps the numbers. For example, if a < b, the initial quotient is zero and the remainder is a. Thus, r_k is smaller than it's predecessor r_k-1.

Since the remainders decrease with every iteration, a remainder r_N must eventually equal 0, at which point this algorithm stops. The final non-zero remainder r_N-1 is the greatest common divisor for a and b.

g = gcd(a, b) = gcd(b, r₀) = gcd(r₀, r₁) = … = gcd(r_N−2, r_N−1) = r_N−1.

For proof of the algorithm, visit here.

A simple implementation of Euclid's GCD algorithm in C++ would be,

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

Once we calculate the GCD of two numbers, we can calculate the LCM very easily.

int lcm(int a,int b)
{
    return (a*b)/gcd(a,b);
}

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's primality, 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 sqrt(n). If

This contradicts our assumption that a*b = n. Hence one of them has to be less than 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=0;i*i<=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

In mathematics, the Sieve of Eratosthenes is a very simple algorithm of finding all prime numbers upto 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.

Let's look into a simple implementation of the sieve in C++.

//Finding all primes within the range [1,n)
void sieve(int n)
{
    vector<int> 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;
}