# Prime Lovers

Well, I might not define What’s A prime Number..(A number divisible only by 1 and itself :P)

But what if i tell u to find all prime numbers below 100.

Fine..!! U can either find it manually or if u r smart Enough u will make Code for it!!Simple enough?

Naive Approach:

Here is a Pseudo Code for it:

Let n be a number To check for “Primality”:

start i from 2 to n-1

Check whether n is divisible by i or not

If(yes)

stop here..Number is Not prime.

if u reach till n-1 and it is not divisible then n is prime!!

A More Optimised Version:

start i from 2 to squareroot(n)

Seams to be Easy enough!!

But Might be too Boring for the computer too, to calculate for each number untill 100.

What if i tell u to calculate all Prime numbers below 10^6 ?(Yeah 10 raise to 6 :P)

Hmmm..Even this program will take a long time.

Well Dont be Disheartened!!

Here comes the Most exciting Part.

There is an Excellent Method To calculate all primes below a given large Number:

*Sieve Of Eratosthenes:*

*Sieve Of Eratosthenes:*

*Fun starts Here!!:*

A step by step Approach:

Let N be a number Below which u want to find all Prime Numbers

- Create a list of consecutive integers from 2 to
*n*: (2, 3, 4, …,*n*). - Initially, let
*p*equal 2, the first prime number. - Starting from
*p*,Cut Down all Numbers(Except p) multiple of p. i.e. 2*p*, 3*p*, 4*p*, etc.; note that some of them may have already been marked. - Find the first number greater than
*p*that hasn’t been cut down. If there was no such number, stop. Otherwise, let*p*now equal this number (which is the next prime), and repeat from step 3.

Well to understand better here is an Example.

Find Primes Below 30.

First generate a list of integers from 2 to 30:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

First number in the list is 2; cross out every 2nd number in the list after it (by counting up in increments of 2), i.e. all the multiples of 2:

2 3~~4~~5~~6~~7~~8~~9~~10~~11~~12~~13~~14~~15~~16~~17~~18~~19~~20~~21~~22~~23~~24~~25~~26~~27~~28~~29~~30~~

Next number in the list after 2 is 3; cross out every 3rd number in the list after it (by counting up in increments of 3), i.e. all the multiples of 3:

2 3~~4~~5~~6~~7~~8~~~~9~~~~10~~11~~12~~13~~14~~~~15~~~~16~~17~~18~~19~~20~~~~21~~~~22~~23~~24~~25~~26~~~~27~~~~28~~29~~30~~

Next number not yet crossed out in the list after 3 is 5; cross out every 5th number in the list after it (by counting up in increments of 5), i.e. all the multiples of 5:

2 3~~4~~5~~6~~7~~8~~~~9~~~~10~~11~~12~~13~~14~~~~15~~~~16~~17~~18~~19~~20~~~~21~~~~22~~23~~24~~~~25~~~~26~~~~27~~~~28~~29~~30~~

Next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every 7th number in the list after it, but they are all already crossed out at this point, as these numbers (14, 21, 28) are also multiples of smaller primes because 7*7 is greater than 30. The numbers left not crossed out in the list at this point are all the prime numbers below 30:

2 3 5 7 11 13 17 19 23 29

(Images- Wiki)

Well this might seam easy !!But tricky while programming!!

Pseudo Code:

“isPrime” is a boolean (True or False) Array

Initialize all values to true.(Assuming All values uptil k is a prime Number)

At the end of Code if u want to find if ‘x’ is prime or not,Just check bool value of isPrime[x]. If true then its prime else not a prime.

1)isPrime[0] = false

2)isPrime[1] = false

3)for i = 2 to K do

isPrime[i] = true //Initializing all values to true

4)for i = 2 to sqrt(K) do

if isPrime[i] then

for j = i^2, i^2+i, i^2+2*i, …, k: //Note that it starts from i square and not 2*i.They have already been checked

isPrime[j] = false //they all are Not Primes

All the true values in array suggests that its an prime number (Since it was not a multiple of any number!!!!)

The Two Advantages of this method:

1)Simple approach and Faster than the Naive one.

2)Easily finds the no of Primes below A certain number .

As we have Precalculated all primes, its called memoization,and it can be accessed as and when required.

**Just for comparing the difference in time taken:-**

naive algo : O(n^2) or O(n*sqrt(n))

sieve : O(n(log n)(log(log n)))

which is a big difference for large values of n.

Here is the implementaion:

// This code checks whether a given number is prime or not. #include<iostream>; using namespace std; int main(){ bool isPrime[1000007]; isPrime[0] = false; isPrime[1] = false; for (int i = 2 ;i<1000005;i++) isPrime[i] = true; for (int i = 2;i*i<1000005;i++){ if(isPrime[i]){ for (int j = i * i;j<1000005;j+=i) isPrime[j] = false; } } // Here 1000003 is checked for being prime. // To check any other number replace 1000003 with it. if(isPrime[1000003]){ cout<<"Yep it's prime!!!"; }else{ cout<<"Nahh it's not prime!!!"; } return 0; }

Seive Approach : Seive

Any comments are welcomed.Happy Coding 🙂