質數 - Sieve theory

wc_big_pig天尊

#include<string.h>
#include<stdio.h>
#include<memory.h>
#define MAXSIEVE 20000000 // All prime numbers up to this
#define MAXSIEVEHALF 10000000
#define MAXSQRT 2237 // sqrt(MAXSIEVE)/2
#define isprime(n) (a[(n)>>4]&(1<<(((n)>>1)&7))) // Works when n is odd
char a[MAXSIEVE/16+2];
int b[107408];
int main(){
int i,j;
int input;
int counter=2;
memset(a,255,sizeof(a));
a[0]=0xFE;
for(i=1;i<MAXSQRT;i++) //從1到最大的可能質數
if (a[i>>3]&(1<<(i&7))) //如果那個數是質數
for(j=2*i*(i+1);j<MAXSIEVEHALF;j+=i+i+1) //把那的質數所有的倍數 都設為不是質數
a[j>>3]&=~(1<<(j&7));


return 0;
}