素数的倍数一定是合数， 用素数的倍数筛掉合数
埃式筛：复杂度O(nloglogn)
long long cnt, Prime[Max]; bool visit[Max]; void Sieve() { cnt = 0; visit[0] = visit[1] = 0; for(long long i = 2; i <= Max; i++) { if(!visit[i]) { Prime[cnt++] = i; for(long long j = i * i; j <= Max; j += i) { visit[j] = 1; } } } }欧拉筛：O(n)
#include <cstring> using namespace std; int prime[1100000], primesize, phi[11000000]; bool visit[11000000]; void Sieve() { int cnt = 0; visit[1] = 1; for(int i = 2; i <= MAX; i++) { if(!visit[i]) prime[cnt++] = i; for(int j = 0; j < cnt && i * prime[j] <= MAX; j++) { visit[i * prime[j]] = 0; //质数prime[j]是合数i*prime[j]的最小素因子 if(i % prime[j] == 0) break; //break的原因是防止一个合数被筛多次: //i*prime[j+1]这个数肯定能被prime[j]乘以某个数筛掉, //因为i中包含prime[j] } } }素数定理：
