素数筛法基础

2024 年 1 月 1 日全文共 33 字预计阅读 1 分钟

改进版埃氏筛

对于每个数 $x$ ，只需要从 $x^2$ 开始，把 $x^2 , (x+1)x ,..., (n/x)x$ 筛去即可

for (int i = 2; i <= n; i++) {
    if (flag[i]) continue;
    p[cnt++] = i;
    for (int j = i; j <= n / i; j++) flag[i * j] = 1;
}

评论