中级 · 循环逻辑

素数判断

读一个整数,输出它是不是素数。题目好懂 — 但这是第一道"怎么循环"和"要不要循环"一样重要的题。

一句话答案只试到 √N，一遇到能整除的就停下 —— 1 不是素数、2 是，而 √N 这个上界让 N = 10⁶ 时循环只有一千步左右。

题目

输入: 一个整数 N(1 ≤ N ≤ 1,000,000)。

输出: 是素数输出 prime,否则 not prime（一字不差）。

样例:

输入输出
17prime
18not prime

素数恰好有两个因数:1 和它自己。所以 1 不是素数,2 是唯一的偶素数。

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 假设、证伪、下结论

从 bool prime = true; 开始。循环试探因数;一旦整除(n % i == 0),置 prime = false; 并 break; — 一个反例就够了。之后根据旗子输出。

提示 2 — 不用试到 N

如果 N 有大于 √N 的因数,它必然也有小于 √N 的因数(两者配对:d × (N/d) = N)。所以循环条件 i * i <= n 就够了 — N = 1,000,000 时是 1000 个候选,不是一百万个。边界:N = 1 不是素数;N = 2 是。

题解（先自己试试！） 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool prime = true;
    if (n < 2) prime = false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            prime = false;
            break;
        }
    }
    if (prime) cout << "prime" << endl;
    else cout << "not prime" << endl;
    return 0;
}

这里的三个想法 — 先假设再证伪、首个反例就 break、√N 捷径 — 贯穿所有数论题。好目标:打印 ≤ N 的全部素数（加一层外循环,或者研究埃氏筛 — 下一题就是）。

深度解析

为什么这样做对

先假设、再反驳：一开始认为它是素数，然后只找反例。这个形状是你以后写的每一个校验循环的骨架。

代价

加上 i * i <= n 的界是 O(√n)。100 万只需 1000 次循环而不是 100 万次——一行代码换一千倍。

常见错法

  • i <= sqrt(n) 每轮都算一次浮点开方，还会在边界上被舍入误差坑。i * i <= n 既精确又快。
  • 漏掉 n < 2 的判断，0 和 1 就被判成素数了。

下一步

把 N 以内的素数全部求出来：素数计数。

记住这两句

  • 因数成对出现——到 √n 就该停。
  • 1 不是素数；2 是唯一的偶素数。
🐞 这段是错的 —— 点开,亲手让它挂一次

i * i < n 漏掉了平方数

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool prime = true;
    if (n < 2) prime = false;
    for (int i = 2; i * i < n; i++) {
        if (n % i == 0) {
            prime = false;
            break;
        }
    }
    if (prime) cout << "prime" << endl;
    else cout << "not prime" << endl;
    return 0;
}