TB椰程 TypeBuddy 打字搭子

埃氏筛素数表

CSP-J · 编程模板 · 片段 · cpp · 难度 3/5 · 共 362 字

从 i 的平方开始标记倍数，一次筛出素数表

  • 素数
  • 筛法

前置内容

正文

// ── 埃氏筛：批量求素数 ──
// 素数的倍数一定不是素数
// 提前划掉即可
int is_prime[100005];
// 1=暂时算素数，0=已划掉
for (int i = 2; i <= n; i++)
    is_prime[i] = 1;
for (int i = 2; i * i <= n; i++) {
    // 已被划掉的跳过
    if (!is_prime[i]) continue;
    // 从 i*i 开始划：
    // 更小的倍数早划过了
    for (int j = i * i; j <= n; j += i) {
        is_prime[j] = 0;
    }
}
// 总复杂度约 O(n log log n)
// 比一个个试除快得多

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK