Sieve of Erathosthenes : a find of quick ways to generate primes upto generally less than a million . below is the code for it .
what the sieve of eratosthenes does it that it eliminates all the multiples of previously determined primes .
optimization 1: start eliminating numbers for prime i starting from i*i
optimization 2: i ends at i*i<upper since any composite below upper will atleast have one prime factor below sqrt(upper)
optimization 3 : any prime can be of type 6k+1 or 6k+5 only .
Using these optimization I have coded the following program which on my i-5 machine takes 2.5s to calculate primes upto 9e7.
what the sieve of eratosthenes does it that it eliminates all the multiples of previously determined primes .
optimization 1: start eliminating numbers for prime i starting from i*i
optimization 2: i ends at i*i<upper since any composite below upper will atleast have one prime factor below sqrt(upper)
optimization 3 : any prime can be of type 6k+1 or 6k+5 only .
Using these optimization I have coded the following program which on my i-5 machine takes 2.5s to calculate primes upto 9e7.
No comments:
Post a Comment