» » Generating Prime (Sieve)

Generating Prime (Sieve)

   4:34 PM       

 
#define mx 100000
#define chkp(n) (prm[n>>6]&(1<<((n>>1)&31)))
#define genp(n) (prm[n>>6]|=(1<<((n>>1)&31)))
#define PrimeLimit 10000000
int prm[PrimeLimit / 64], prime[mx], prlen;
void GeneratePrime(){
	int i,j,sqrtN;
	prlen = 0;
	prime[prlen++]=2;
	sqrtN = ( int ) sqrt ( ( double ) PrimeLimit ) + 1;
	for(i=3;i<sqrtN;i+=2)if(!chkp(i)){
			prime[prlen++] = i;
			for(j=(i*i);j<PrimeLimit;j+=(i<<1))genp(j);
	}
	for(;i<PrimeLimit;i+=2)if(!chkp(i))prime[prlen++]=i;
}