Question 20

把上界改成 i <= n 的后果

如果将 `for (int i = 2; i * i <= n; i++)` 改为 `for (int i = 2; i <= n; i++)`,输入 10 时程序的输出是什么?

单项选择阅读程序3难度 中等

正确答案

A. 将不能正确计算 10 以内素数个数及其和

一句话考点

如果把循环跑到 `i == n`,那么任何 `n > 1` 都会因为 `n % n == 0` 被错误判成非素数。

素数程序修改

Shared Context

阅读程序(1)素数统计

这一组程序围绕素数判断函数展开,分别统计素数个数和素数和。

核心算法

试除法判断素数,只需要枚举到 sqrt(n)。

高频陷阱

把循环条件改成 `i <= n` 会让所有大于 1 的数都被判成非素数。

题型定位

属于“读懂函数职责 + 模拟几个样例”的标准阅读程序题。

cpp

共享程序片段
#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 countPrimes(int n) {
  int count = 0;
  for (int i = 2; i <= n; i++) {
    if (isPrime(i)) {
      count++;
    }
  }
  return count;
}

int sumPrimes(int n) {
  int sum = 0;
  for (int i = 2; i <= n; i++) {
    if (isPrime(i)) {
      sum += i;
    }
  }
  return sum;
}

int main() {
  int x;
  cin >> x;
  cout << countPrimes(x) << " " << sumPrimes(x) << endl;
  return 0;
}

题组阅读提醒

程序先定义 `isPrime` 判断某个整数是不是素数,再通过 `countPrimes` 与 `sumPrimes` 分别统计 2 到 n 的素数个数和素数和。

关键观察点有两个:一是 `i * i <= n` 代表只需枚举到平方根;二是两个统计函数都采用从 2 到 n 的线性扫描,因此输出是“包含 n 在内”的统计结果。

本题属于第 阅读程序 分区,题组覆盖题号: 16、17、18、19、20

Prompt

题目与选项

如果将 `for (int i = 2; i * i <= n; i++)` 改为 `for (int i = 2; i <= n; i++)`,输入 10 时程序的输出是什么?

A. 将不能正确计算 10 以内素数个数及其和

B. 仍然输出 4 和 17

C. 输出 3 和 10

D. 输出结果不变,但运行时间更短

Quick Check

做题抓手

先判断题型

先定位知识点,再决定是公式套用、手推样例还是结构重建。

再核对边界

第一轮很爱在闭区间、下标偏移、递归终止条件和布尔返回值上设陷阱。

最后看输出层次

尤其是阅读程序题,要分清函数返回值、变量值和最终打印值是不是同一件事。

Explanation

详细讲解

  1. Step 1

    原本只枚举到平方根,不会检查 `i == n`。改成 `i <= n` 后,当 `n` 本身是素数时,循环最终会跑到 `i = n`。

  2. Step 2

    此时 `n % i == 0` 成立,函数就会返回 `false`,导致所有大于 1 的数都被错判为非素数。

  3. Step 3

    因此程序不再能正确统计 10 以内素数个数和素数和,正确答案是 A。

Pitfalls

易错点

  • 只看到循环次数变多,就想当然地认为“只是变慢,不影响结果”。
  • 没有意识到 `n` 自身也是它的因子,`n % n` 一定等于 0。

Extend

拓展补充

  • 判断素数时,枚举上界不能写到 n 自己,否则会把所有素数误杀。

返回总览

回到整套试卷

返回题目总览页,继续从目录、知识图谱或其他分区进入。

所属分区

返回 阅读程序

回到首页对应分区,继续顺序刷题或查看同类知识点。

上一题

第 19 题

sumPrimes(50) 输出

下一题

第 21 题

样例 {10,15,20} 的输出