TB椰程 TypeBuddy 打字搭子

求素数

CSP-J · 编程模板 · 代码 · cpp · 难度 2/5 · 共 307 字

试除法判素数，i * i <= n 剪枝

  • 素数
  • 函数

前置内容

正文

// ── 试除法判断素数 ──
// 素数：大于 1，且只能被 1
// 和它自己整除
int is_prime(int n) {
    // 0 和 1 都不是素数
    if (n < 2) return 0;
    // 因子成对出现：有大因子必有
    // 对应小因子，扫到 sqrt(n) 即可
    for (int i = 2; i * i <= n; i++) {
        // 找到因子，立即判负
        if (n % i == 0) return 0;
    }
    return 1;
}
// 复杂度 O(sqrt(n))
// 批量求素数用筛法更快

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

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