素数筛（欧拉筛）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool numlist[100000001];
int prime[20000001], cnt;
auto work=[&](int n) -> void
{
    for(int i=2; i <= n; i++){
	    if(numlist[i] == false)
	    	prime[++cnt] = i;
	    for(int j = 1; j <= cnt && i * prime[j] <= n; j++){
	        numlist[i*prime[j]] = 1;
	    	if(i % prime[j] == 0)
                break;
		} 
	}
}

函数筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
auto getMu=[&]()->void{
    mu[1] = 1;
    for (int i = 2; i <= n; ++i) {
	    if (!flg[i]) p[++tot] = i, mu[i] = -1;
	    for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
	    flg[i * p[j]] = 1;
	    if (i % p[j] == 0) {
		    mu[i * p[j]] = 0;
		    break;
    }
    mu[i * p[j]] = -mu[i];
    }
}
};