线性筛

证明

正确性证明

对合数 \(x = py\)，其中 \(p\) 是 \(x\) 的最小质因子。

考虑当 \(i = y\) 时，枚举已筛出的质数 \(j\)。

由于 \(p\) 是最小质因子，所以 \(i\) 不含小于 \(p\) 的质因子，所以在枚举到 \(p\) 前，i % j = 0 不会成立，循环不会终止。

这就证明了 \(x\) 会被筛掉。

线性时间复杂度证明

假设 \(x = py = qz\)，其中 \(p\) 是 \(x\) 的最小质因子，q 是另一质因子。

根据唯一分解定理，\(z\) 一定含有质因子 \(p\)，且 \(p < q\)。

则 \(i = z, j = p\) 时，i % j = 0 会先一步成立，循环终止，质数不会枚举到 \(q\)。

考察证明过程可以发现，\(j\) 就是合数 \(i \times j\) 的最小质因子。

筛出质数

Warning

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

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;
        }
    }
}

同时计算最小质因子

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;
        }
    }
}