Laziness is a virtue. If not I wouldn’t write this post on my two day experiment with sieve algorithm. By now I realized how worse an algorithm can get implemented. Below is my version of code to generate prime numbers up to n. I am trying to improve it and make it clean, clear and short. Once I am done I will update the below code. I got the first inspiration from a python recipe in Active State community but later found my version scales better than that for an input say up to 10 million (Sieve is supposed to work efficiently up to 10 million). I found not just a marginal but a considerable difference in terms of execution efficiency.
Below is the algorithm in bird’s eye view.
Step 1: Create an array(say s[]) of odd numbers starting with 3 up to n
Since sieve suggest to start with all natural numbers from 2, we will start ahead with 3 discarding 2 and its multiples as we know they are not prime
Step 2: create another array(say p[]) with first element 2.(2 is a prime ).Now first non zero element(say m) of s is a prime. append this element to p and mark it 0 in s.
Step 3: find all the multiples of m(first its 3)
We can straight away go to the square of the number since all its preceding multiples will be deleted in the previous steps. Formula for index of m**2 is ind=(m*(m-1)/2)+s.index(m). Now jump to all the multiples by ind=ind+m and make it 0 s[ind]=0
Step 4: Loop steps 2 and 3 until square of m is greater than largest element of array s
Step 5: Append all the non zero element of s to p. There we go. P is now a list of prime numbers from 2 to n
Below code is updated to reduce the cost of function call in the previous version. I think now its short and clear.
Code moved to : http://ideone.com/UoqXu
Result: It takes less that 20 seconds to find the prime up to 10 million(10^7). But this code will neck bury any 2GB ram with an input of 100 billion(10^8). Probably in the next version memory handling will have a whole new definition