C++教程

筛法

对应练习:ACWING868

代码1:埃氏筛法

    ans//素数个数, 
    n//上限,
    f[1000001]//是否是素数(0是),
    
void pre(int n) {
    f[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!f[i]) {
            ans++;//计数:质数的个数
            for (int j = i * 2;  j <= n; j += i)
                f[j] = 1;
        }
    }
}

代码2:线性筛法



    ans//素数个数, 
    n//上限,
    p[1000001]//是否是素数(0是),
    vis[1000005];

void pre() {
    p[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i])
            p[++ans] = i; //新的素数，加入素数表
        for (int j = 1; i * p[j] <= n; j++) {
            vis[i * p[j]] = 1;
            if (i % p[j] == 0)
                break;
        }
    }
}