Prime numbers have been understood at least since the Ancient Greeks, and possibly since the Ancient Egyptians. In modern times their study has intensified greatly due to their usefulness, notably in encryption, and because computers enable them to be calculated to a massively higher level than could be done by hand.

The best know (and according to Wikipedia still the most widely used) method for identifying them is the Sieve of Eratosthenes, which I will implement here in JavaScript.

The Sieve of Eratosthenes

The algorithm is described in full on Wikipedia, and you might like to take a look at the article.

Eratosthenes of Cyrene c276 BC to c195/194 BC

To summarize the process:

1. Create a list of integers from 2 to the highest number you want to check, marking them all as prime
2. Initialize a variable p to 2 (the lowest prime)
3. Mark all multiples of p as composite (ie. non-prime)
4. Set p to the next number marked as prime
5. Repeat 3 and 4 until no subsequent primes are found.

The algorithm as it stands has some glaring inefficiencies and the Wikipedia article cited above does include some refinements and alternatives.

The Code

The files for this project can be downloaded as a zip from the Downloads page, or cloned/downloaded from Github. They include an HTML page, a graphic, a CSS file and a JavaScript file containing a function to output text to the page, The core file is sieveoferatosthenes.js which I will list and describe below.

Source Code Links

ZIP File
GitHub

sieveoferatosthenes.js (part 1)

window.onload = function()
{
    writeToConsole("Sieve of Eratosthenes<br/><br/>", "console");

    const max = 100;
    let p = 2;

    prime_flags = initializePrimeFlags(max);

    writeToConsole("Initial state: all marked as prime<br/>", "console");

    outputAll(prime_flags, 10);

    writeToConsole("<br/>Running Sieve of Eratosthenes...<br/>", "console");

    while(p != -1)
    {
        markMultiples(prime_flags, p);

        p = findNextPrime(prime_flags, p);
    }

    writeToConsole("<br/>Composite numbers now identified<br/>", "console");

    outputAll(prime_flags, 10);

    writeToConsole("<br/>", "console");
}

In the onload event handler we firstly create a couple of variables: the maximum number we want to check for "primeness" and the current value of p. We then call initializePrimeFlags to get an array of Booleans of size max.

As you may have realised, although the Sieve of Eratosthenes is usually described as an algorithm for identifying prime numbers it is actually the opposite. It starts off with the assumption that all numbers are prime, and then identifies the ones that are not. The values of prime_flags are therefore initialized to true, and to emphasize this I have called outputAll before the sieving process to show that all the numbers are currently flagged as primes.

We then enter a while loop, calling functions to flag multiples of p as composite and then getting the next prime in the list. The latter function returns -1 if there are none left, so that value is used as the exit condition of the while loop.

The process is now complete so we just call output_all again to show which numbers are prime and which are composite.

Now we just need to implement the four functions called in onload, starting with initializePrimeFlags.

sieveoferatosthenes.js (part 2)

function initializePrimeFlags(max)
{
    prime_flags = [];

    for(let i = 2; i <= max; i++)
    {
        prime_flags[i] = true;
    }

    return prime_flags;
}

This function is quite straightforward - just create an array and set the required number of values to true in a loop. The indexes of these Booleans correspond to the actual numbers they are flagging. This means that as we don't use 0 and 1 there are two Boolean's worth of memory wasted, but I hope you will agree that the convenience of exact indexing outweighs a tiny amount of wasted memory!

Next up is the markMultiples function.

sieveoferatosthenes.js (part 3)

function markMultiples(prime_flags, p)
{
    let multiplier = 2;
    let i = p * multiplier;
    let l = prime_flags.length;

    if(i <= l)
    {
        while(i <= l)
        {
            prime_flags[i] = false;

            multiplier++;

            i = p * multiplier;
        }
    }
}

Firstly we create a couple of variables, the multiplier set to 2 and i set to p * multiplier to give us the first value to flag as non-prime. After checking that i hasn't blown through the end of the data we enter a while loop, setting the flag to false, incrementing the multiplier, and then calculating the next value of i or in other words the next value to be flagged as non-prime. The loop continues until we run past max.

Basically what we are doing here is multiplying the current prime by 2, 3, 4 etc. and marking the result as non-prime until we get past max. Note this is one of the inefficiencies in the basic algorithm - we may be marking numbers as non-prime which have already been flagged as multiples of lower primes. For example, 6 would be marked as non-prime because it is a multiple of 2, but would be marked non-prime again as a multiple of 3.

sieveoferatosthenes.js (part 4)

function findNextPrime(prime_flags, current)
{
    let l = prime_flags.length;

    for(let i = current + 1; i <= l; i++)
    {
        if(prime_flags[i] == true)
        {
            return i;
        }
    }

    return -1;
}

The findNextPrime function searches through the flags for the next prime, starting at the one after the current. If one is found it is returned; if the loop completes without a prime being found the function returns -1. (Remember that in onload we use -1 as the terminating condition for the while loop.)

sieveoferatosthenes.js (part 5)

function outputAll(prime_flags, columncount)
{
    let n;

    writeToConsole("<span class='greenbg'>PRIME</span> ", "console");
    writeToConsole("<span class='redbg'>COMPOSITE</span><br/><br/>    ", "console");

    for(let i = 2, l = prime_flags.length; i < l; i++)
    {
        n = String(i).padStart(4, " ").replace(/ /g, " ");

        if(prime_flags[i] == false)
        {
            writeToConsole(" <span class='redbg'>" + n + "</span>", "console");
        }
        else
        {
            writeToConsole(" <span class='greenbg'>" + n + "</span>", "console");
        }

        if(i % columncount == 0)
        {
            writeToConsole("<br/><br/>", "console");
        }
    }
}

This just iterates the data, outputting the values with red or green background classes to indicate their status as composite or prime - note we start off with a key to the colour coding.

The function takes a columncount argument so if we have run out of columns we print a new line to go back to the first column. This is calculated using the modulus (remainder) operator %, for example if we asked for 10 columns and have just printed value 30, 30 % 10 = 0 so we output two break elements. For any value of i which is not a multiple of 10 the modulus will be non-zero so puts is breaks are not output.

Now open sieveoferatosthenes.htm which looks something like this.

I have only taken it up to 100 but the possibilities are infinite...!