#Day 3

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

A

prime numberis a wholenumbergreater than 1, whose only two whole-numberfactors 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).

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).

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

We have the final table as in 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

**Where n is the number up to which the prime numbers need to be calculated.**

*n*).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.