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; //防止重复标记
}
}
}