While attempting Project Euler, I came across a fun mathematical concept known as the sieve of Eratosthenes. It was a systematic and logical way of finding prime numbers devised by the ancient Greek, Eratosthenes. Although there were many articles regarding this method, I still found the concept challenging to grasp in terms of code. I was just an average Joe in terms of IQ, hence I thought of writing this page to alleviate the struggle of anyone after me.
The problem of summing up all prime numbers below 2 million.
int n=2000000;The above method was extremely inefficient. It took about 7 mins on my laptop to finish running. The reason being the program was using brute force to check every single number below 2 million as to whether it was a prime. Although we can make it better by using:
for(int i=2;i*i<=num;i++)This would drastically cut down the execution time to about 0.9s.
Side note: it took me a while to figure out how to accurately get the square root of n. At first I tried using Math.round() to achieve a “long” data type. However, this gave an answer that was quite off, due to rounding issues. Then I remembered that java allows arithmetic calculation within the header of for loop, hence this i*i.
As to why we only needed to check prime factors till square root of n, it goes back to the sieve. Although at one point of time, I only knew this because of stackoverflow. There was no real understanding, until I read the sieve of Eratosthenes.
Pure math, using n=21 as example:
step 1: Take 1st prime,2, and sq it.You get 4. Add the prime,2, to 4 and so on. Cancel all these numbers.step 2: Do the same for 2nd prime and so forth.
As you can infer, all we needed to check was until 3, which was below the sqrt of 21, 4.583(3sf). The reason being anything after sq root of n will either be a prime or have a factor below the sq root of n.
Below was the code for the sieve in java. I adapted the code from somewhere online and I am only using this as educational material to explain the logic.
Although admittedly, java was not the best language to implement this due to the memory allocation in the array part. Nevertheless, it was doable, executing at 0.2s.
Note:
boolean prime[] = new boolean[n+1];The n+1 was there due to the fact that arrays start from 0. We first declared every slot in this boolean array as true.
for(int p = 2; p*p <=n; p++)This was the same concept, checking limit till square root of n.
if(prime[p] == true)
{
for(int i = p*p; i <= n; i += p)
prime[i] = false;
}prime[p] started from 2. We then took the sq of it, which was 4, and declared it false. This was very similar to filling in the cell, in our math example. After that, we added 2 there-forth. This was the essence of our code.
We had achieved what we set out for, which was a code implementation of the 2 thousand year old concept. We can now find any prime number efficiently using the sieve of Eratosthenes!
I hope you found this article informative and simple :) Happy coding.
