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

One thought on “Finding all prime numbers

  1. This is fascinating stuff. Prime numbers have always interested me.
    By chance I discovered a way to factorize a number without having to divide anything. It turns out some easily-generated sequences have such a relationship that unless a term from one can be found in the other, then the value of n used to generate one of those sequences must be prime. These sequences need only a number of terms equal to a quarter of n and, thanks to a handy mathematical law it, each term need not have any more than a very low number of digits no matter how large the value of n. It seems to me it would be very easy for a powerful computer to generate and sort through the two sets of data looking for a match. Much easier than the current method of trying to divide huge numbers into huge numbers. Do you have any thoughts on this?

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s