Finding a prime up to a limit is one of the basic programs and there are lot of ways to approach this. Most common is the trial division method where we check if a number is prime by checking against numbers from 2 to N-1.This will take a lot of time as we need to check against so many numbers. Here we have an ancient algorithm which really simplifies the problem time complexity.

I will take an example.Lets say we need to compute Prime numbers upto 12. Then first we make assumption that all numbers are prime i,e 2,3,4,5,6,7,8,9,10,11,12

Then we go from the first index that's 2 and say if its prime then all its multiple are not prime.

Then cancel all the prime's multiple that is.

2,3,5,7,9,11

Now for 3

2,3,5,7,11

Now continue till all the numbers are checked,as in our case remaining would be all prime.

Source Code:

#include <iostream>

#include<malloc.h>

#include<math.h>

#include<cstring>

#define ll long long

using namespace std;

int main(){

cout<<"**Find prime numbers upto N**\nEnter N value:";

ll N;

cin>>N;

ll *Prim=(ll *)malloc((N+1)*sizeof(ll));

for(int i=0;i<=N;i++)Prim[i]=1;

Prim[0]=Prim[1]=0;

for(int i=2;i<=sqrt(N);i++){

if(Prim[i]==1)

for(int j=2;i*j<=N;j++){

Prim[j*i]=0;

}

}

cout<<"Prime numbers\n";

for(int i=0;i<=N;i++){

if(Prim[i]==1)

cout<<i<<" ";

}

return 0;

}

I will take an example.Lets say we need to compute Prime numbers upto 12. Then first we make assumption that all numbers are prime i,e 2,3,4,5,6,7,8,9,10,11,12

Then we go from the first index that's 2 and say if its prime then all its multiple are not prime.

Then cancel all the prime's multiple that is.

2,3,5,7,9,11

Now for 3

2,3,5,7,11

Now continue till all the numbers are checked,as in our case remaining would be all prime.

Source Code:

#include <iostream>

#include<malloc.h>

#include<math.h>

#include<cstring>

#define ll long long

using namespace std;

int main(){

cout<<"**Find prime numbers upto N**\nEnter N value:";

ll N;

cin>>N;

ll *Prim=(ll *)malloc((N+1)*sizeof(ll));

for(int i=0;i<=N;i++)Prim[i]=1;

Prim[0]=Prim[1]=0;

for(int i=2;i<=sqrt(N);i++){

if(Prim[i]==1)

for(int j=2;i*j<=N;j++){

Prim[j*i]=0;

}

}

cout<<"Prime numbers\n";

for(int i=0;i<=N;i++){

if(Prim[i]==1)

cout<<i<<" ";

}

return 0;

}