Sam Nardoni

There are hundreds of different ways of generating prime numbers; some are fast but memory-hungry, others are slow but use only the space they need.

Generating 2,000,000 primes by means of looping through every number and checking whether it is divisible by more than 2 numbers is awfully slow. Don't fret, there is another method; more memory-hungry, but lightning fast. It's know as the sieve approach.

The sieve approach works by "sieving" all of the prime numbers.

First, there needs to be an array of booleans as big as the limit of primes you need to calculate. For example, we need to calculate all prime numbers below 2,000,000 - so we need an array of 2,000,000 booleans. All of these booleans should be set to true by default.

Next up, comes the sieving part. Starting at 2, we see whether this is currently marked as a prime number (this is the beginning, so it will be). Now we know that any multiple of 2 (that's bigger than 2) is not going to be a prime number. So we loop through every multiple of 2, marking it as not a prime number (setting the boolean to false), up until the end of the array. Now we move on to the next number, 3. We loop through all of the multiples of 3, and mark them as not prime numbers. After this has looped through every number, we are left with an array of booleans. The index of every boolean that is set to true is a prime number.

There is also nice demo online which shows you it happening.

The only addition we need to make is to keep a running total.

The finished product: