信奥一本通C++第2030题找素数的解题思路和代码实现是什么？

信息学奥赛一本通C++第2030题【例4.16】找素数，主要考察对素数概念的理解及循环结构的运用。

解题思路

素数是大于1且只能被1和它本身整除的自然数。判断一个数 n 是否为素数，基本方法是试除法：从2开始逐一尝试能否整除 n。若存在能整除的数，则 n 不是素数；若直到 n-1 都无法整除，则 n 是素数。

优化策略：只需检查到 √n 即可。因为如果 n 有一个大于 √n 的因数 a，那么必然存在一个小于等于 √n 的因数 b（即 n = a × b）。这样可将时间复杂度从 O(n) 降至 O(√n)。

代码实现

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    if (isPrime(n)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

注：具体输入输出格式需以实际题目描述为准，上述代码为通用素数判断模板。

步骤与判断依据

1. 处理边界条件：小于等于1的整数直接判定为非素数。
2. 设置循环变量 i 从2开始，终止条件为 i × i ≤ n。
3. 在循环体内用取模运算 n % i == 0 判断是否整除，若成立则立即返回非素数。
4. 循环正常结束未触发返回，则判定为素数。

适用条件

该试除法适用于单个数值较小（如 n ≤ 10^9）的素数判定场景。若需在较大范围内批量筛选素数，应改用埃拉托斯特尼筛法（Sieve of Eratosthenes）。

常见误区

• 忽略1不是素数这一前提条件，导致边界判断错误。
• 循环条件写成 i < n 而非 i * i <= n，在数据量较大时会导致超时。
• 使用 sqrt(n) 作为循环条件时，因浮点数精度问题可能产生误差，推荐使用 i * i <= n 进行整数比较。