Sieve of Eratosthenes(Primes up to n)

 

#Day 3

Sieve of Eratosthenes is the algorithm to find all the prime numbers up to a number.

A prime number is a whole number greater than 1, whose only two whole-number factors are 1 and itself.

Basic idea for this algorithm is to mark all the composite numbers up to n and return the rest as primes. For this algorithm, we initialize an array of size n+1 with 0 as all the values(Image:1).

 

seive1
Image 1

 

The value of each index suggests if the index of the array is prime or not. If the primeTable[index]==1, then index is prime. For the sake of example, let’s take n =10.

To make this table following pseudo code can be used.

for i from 2 to √n:

if primeTable[i]==0:

temp = 2*i

while temp <=n:

primeTable[temp]=1

temp = temp + i

According to above pseudo code, we start with index=2 and fill all the multiples of 2 with 1. (image: 2)

*All the multiples of a prime number are composite numbers. So we mark them as 1(composite).

seive3
Image: 2

 

Then we do the same with the next index until index <=√n. In this case, next index is 3.(Image: 3)

 

seive4.png
Image: 3

 

 

We have the final table as in image 4.

seive5.png
Image: 4

 

Now as we have marked all the composite numbers, we just need to iterate over the table and all those indexes which have 0 as the value are prime numbers. In above example, those are 2,3,5,7. (Index 0 and 1 are not included because prime numbers are greater than 1)

Time Complexity

The time complexity of this algorithm is O(n log log n). Where n is the number up to which the prime numbers need to be calculated.

Source Code

Source code for the implementation of this problem can be found here. source code link

Hackerrank Problem

This algorithm along with a memoized implementation of factorial can be used to solve this problem.  Source code for the same problem can we found here.

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