跳转至

线性筛

筛出质数

Warning

特别注意第 9 行和第 10 行的顺序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
bitset<MAXn> ved;
vector<int> prime;

int main() {
    for(int i = 2; i <= MAXn - 3; i ++) {
        if(!ved[i]) prime.push_back(i);
        for(int pj : prime) {
            if(i * pj > MAXn - 3) break;
            ved[i * pj] = 1;
            if(i % pj == 0) break;
        }
    }
}

同时计算最小质因子

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
bitset<MAXn> ved;
vector<int> prime;
int mn[MAXn];

int main() {
    for(int i = 2; i <= MAXn - 3; i ++) {
        if(!ved[i]) prime.push_back(i), mn[i] = i;
        for(int pj : prime) {
            if(i * pj > MAXn - 3) break;
            ved[i * pj] = 1;
            mn[i * pj] = pj;
            if(i % pj == 0) break;
        }
    }
}