Finding all prime numbers

Till now I just knew only one way of finding all primes i.e. Sieve of Eratosthenes or space optimized version of the same called segmented sieve or time optimized version called Euler’s Sieve.

All of above work on same fundamentals striking out composite numbers from the beginning and what is remaining are the primes.

Recently I came across another way of finding primes the process is called Sieve of Sundaram.

  • You start with all the integers from 2 to n
  • From the above list remove all numbers which are of the form i + j + 2 * i*j

    1<= i <= j

    i + j + 2 *i * j <= N
  • What is remaining is doubled and incremented by 1 to give all the primes except 2. So basically all odd primes.

Example working:

Let us start with (n = 7) i.e. 1, 2, 3, 4, 5, 6, 7
In first step let us keep i = 1 and j = 1, 2, .. so cross out 1 + 1 + 2*1*1 (=4), 1 + 2 + 2 * 2* 1 (=6) take i = 2 then all are greater than 7 so not needed.
Remaining numbers are 1, 2, 3, 5, 7 So from Sieve of Sundaram all odd primes are:
1*2+1, 2*2+1, 3*2+1 = 3, 5, 7 add 2 and you have your result(all the primes in 1 to n).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s