Checking prime numbers in Sieve method
Last Update: 6 March, 2009

Problem: In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. There are many algorithm to check whether a number is prime or not.
For relatively small numbers, it is possible to just apply trial division to each successive odd number. Prime sieves are almost always faster.

 

My Code:

// C++ code for Generating Prime Number upto N using Sieve metho

#include<cstdio>
#include<cmath>
#include<iostream>

using namespace std;

// if n is prime, then prime[n]==tru
const int limit = 100000;
bool prime[limit];// true not prim
void gen_isprime(void){
	int i,j;
	for(i=0;i<limit;i++)
		prime[i]=true;
	prime[0]=false;
	prime[1]=false;

	for(i=2;i<limit;i++){
		if(prime[i]==false) // not prim
			continue;
		for(j=2*i; j<limit; j+=i)
			prime[j]=false; // not prim
	}
}


int main() {
	//freopen("in.txt","rt",stdin)
	//freopen("out.txt","wt",stdout)

	int test,t;
	gen_isprime();

	cout<<"Give the value of n if you want to see the prime numbers between 1 to n"<<endl;
	while(scanf("%d",&test)==1){
		for(t=1;t<=test;t++){
			if(prime[t]==true)
				cout<<t<<" ";
		}
		cout<<endl;
	}

	
// End of main function.......
return 0;
}


/***  Programmed by:
###########################
##   ~  ORONNO  ~		 ##
## 	CSEDU 12th Batch.	 ##
###########################
Note: This program is not totally
useless. Because, at least, this
might be used as a bad example!!!!
**********************************/