A prime number (or commonly a prime) is a natural number greater than 1 which has exactly two natural divisors (1 and itself). They are widely studied by number theorists and a fairly in competitive programming problems and interview questions. But why?

Well, during 1-2 articles, we will be discussing some interesting uses, properties and means of computing primes that will help us understand why they are popular.

They are used for calculating hash codes

Firstly, a hash table is a data structure that maps values to keys. Hash codes are number codes, computed through a function called a hash function, assigned to complex objects (which are the keys) in order to quickly retrieve them from a hash table. Ideally, a hash function should be injective (no two objects should return the same value). However, in practice, this is a fairly hard task. This is where primes come into play. For example, the widely used function to compute a hash of a string is the following:

Where m and p are some chosen positive integers. This is called a polynomial rolling hash function.
Reasonably, p should be a prime number around the number of characters in the alphabet and m should be a large number (in practice, it should also be prime)

Modern cryptography requires extensive use of prime numbers

Prime numbers are the fundamental tool that the most common type of encryption used today, RSA, uses.
It depends on the fact that the prime factorization of large numbers takes a lot of time: there exists a public key (the product of two large prime numbers) and a secret key (those two large prime numbers). Everyone can use the public key to encrypt messages to send you, but only you can decrypt the message. Anyone else should find the prime factorization of the public key (which right now takes an unreasonable amount of time).

Algorithms related to prime numbers

There are various algorithms related to prime numbers. We will study some approaches and analyse their performance in order to understand them.

Checking whether a number is prime or not

The first algorithms we will look into are those that test for primality. Even though prime factorization is thought to be a computationally difficult problem, primality testing is not, as we will see below.

Naive method

The most naive solution is to use the definition in order to get a correct algorithm:

bool primeCheck(int n) {
    if(n <= 1) return 0;

    for(int i = 2; i < n; i++) 
        if(n % i == 0) /// if i is a divisor of n 
            return 0;

    return 1; /// we haven't found any divisor
}

Without much analysis, we can clearly see that the complexity of the algorithm is O(n), because it checks every number i between 2 and n-1 to see if it divides n.

A rapid, small optimisation can quickly arise if we pay attention to a small observation: any number n won't have any divisors greater than n/2:

bool primeCheck(int n) {
    if(n <= 1) return 0;

    for(int i = 2; i <= n/2; i++) 
        if(n % i == 0) /// if i is a divisor of n 
            return 0;

    return 1; /// we haven't found any divisor
}

The complexity is still O(n), but the runtime should be a little lower than the one of the first version.

O(n) is the worst time complexity we can get and is still polynomial in the size of the input. That is why, as I said above, primality testing is not considered computationally difficult.

Further improvements over the naive method.

A property of the divisibility relation is that if i is a divisor of n, then n/i is a divisor of n. By taking this into account, we can make another optimisation: we only need to check up to the square root of n, because any divisor greater than that would have had a number to pair with in order to get n by multiplying them.
Another improvement we can make is by using another observation: if n is not divisible by 2, then it won't be divisible by any even number. So, we can check if 2 is a divisor of n separately and then only look at odd numbers. With the improvements, the algorithm should look like this:

bool improvedPrimeCheck(int n) {
    if(n <= 1) return 0;
    if(n % 2 == 0) return 0;

    for(int i = 3; i*i <= n; i++)
        if(n % i == 0)
            return 0;

    return 1;
}

The time complexity of the algorithm above has now become O(sqrt(n)).

That's it for this article. During the next article, we will be taking a look into generating prime numbers and prime factorisation, so stay tuned!