C++ – 素数筛

const int MAXN = 1e7 + 100;
int num = 0;       //素数集合的大小 
bool prime[MAXN];  //素数表[prime[i]表示i是否为素数] 
int Prime[MAXN];   //素数集合[Prime[0~num]保存着0~MAXN中的素数]
void make_prime() {
    memset(prime, true, sizeof prime);  //重置素数表，假设都是素数 
    prime[0] = prime[1] = false;        //规定0和1不是素数 
    for(int i = 2; i < MAXN; i++) {     //遍历素数表  
        if(prime[i])
            Prime[num++] = i;   //将素数存入素数集合
        //用每个数*素数集合里的数 
        for(int j = 0; j < num && i * Prime[j] < MAXN; j++) {
            prime[i * Prime[j]] = false;   //标记素数 
            if(!(i % Prime[j])) break;     //防止重复标记 
        }
    }
}