Hello everyone! It has been a while since I have written a blog post on dev.to - I lacked the motivation to do it for quite some time, but now I intend to pick up where I left on my series, The Magic of Computing, more specifically prime numbers. During the previous article, we explored what prime numbers are, some of their basic uses in computer science and some basic algorithms related to them. This article will focus on generating lists of prime numbers.

An influential figure - Eratosthenes of Cyrene

Living for the most part of the 3rd century BC, Eratosthenes of Cyrene was a mathematician who is now considered the Founder of Geography. He was the chief librarian at the Library of Alexandria and the first person to compute an astonishignly accurate calculation of Earth's circumference, in approximately ~240BC, by comparing the positions of the Sun's rays in two locations. His calculations were only several kilometers off. More information on this can be found here
Apart from measuring the Earth, he also introduced an algorithm now considered ancient, but which is still used nowadays in optimised variations. It is called The Sieve of Eratosthenes and is used for finding prime numbers up to any given limit.

The Sieve of Eratosthenes - a simple, yet ingenious approach to generate prime numbers

The algorithm is based on a very simple idea - prime numbers cannot be the multiple of any prime number before them. Let the given limit for our algorithm be called n. Firstly, it considers all numbers, starting from 2, to be prime. Then, incrementally, for every number i from 2 up to n, it checks whether i is prime:

• if i is prime, the algorithm marks all the multiples of i lower than or equal to n as non-prime, or composite.
• if i is not prime, the algorithm continues. The algorithm ends when i has reached n.

Straightforward implementation

Below, you can find a basic C++ implementation of the algorithm, using it to print prime numbers up to a number n.

void sieve(int n) {
    bool prime[n+1]; /// we need the numbers between 1 and n
    for(int i = 0; i <= n; i++)
        prime[i] = 1; /// we consider all number from 0 up to n to be prime

    for(int i = 2; i <= n; i++)
        if(prime[i])
            for(int j = 2*i; j <= n; j += i) /// we take all the multiples of i up to n and mark them as non-rpime
                prime[j] = 0;
    /// while printing, we don't consider 0 and 1 as primes.
    for(int i = 2; i <= n; i++)
        if(prime[i])
            cout << i << ' ';
}

Optimisations

An immediate optimisation comes from something also mentioned in the other article as well: 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. Also, when checking multiples, it is also worth observing that all the numbers less than i*i have already been marked when checking the primes smaller than i.
The implementation with the basic optimisations looks like this:

void sieve(int n) {
    bool prime[n+1]; /// we need the numbers between 1 and n
    for(int i = 0; i <= n; i++)
        prime[i] = 1; /// we consider all number from 0 up to n to be prime

    for(int i = 2; i*i <= n; i++)
        if(prime[i])
            for(int j = i*i; j <= n; j += i) /// we take all the multiples of i up to n and mark them as non-rpime
                prime[j] = 0;
    /// while printing, we don't consider 0 and 1 as primes.
    for(int i = 2; i <= n; i++)
        if(prime[i])
            cout << i << ' ';
}

When dealing with a big n, the sieve can be improved further by only checking odd numbers and only using bits to store the primality (for example, by using bitset). A great article on these optimisations can be found here.
The usage of sieves, such as The Sieve of Eratosthenes, has spawned a new area of expertise, called Sieve Theory.

The article has come to and end. The next article will be the last in which we will explore prime numbers and will be centered upon prime factorisation, so stay tuned!