1 条题解

  • 0
    @ 2026-11-7 21:58:57

    区间素数统计 题解

    思路概述

    本题考察双重嵌套循环(Nested Loops)的使用与标志位控制:

    1. 外层循环:遍历数字 i∈[2,n]i \in [2, n]。
    2. 内层循环:判断数字 ii 是否为质数。 枚举可能的因子 j∈[2,⌊i⌋]j \in [2, \lfloor\sqrt{i}\rfloor]。如果存在某个 jj 满足 i mod j==0i \bmod j == 0,说明 ii 是合数,直接跳出内层循环;若没有找到任何因子,则说明 ii 是质数,计数器加 1。

    参考代码如下:

    int count = 0;
    for (int i = 2; i <= n; i++) {
        bool is_prime = true;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            count++;
        }
    }
    cout << count << "\n";
    

    正确性说明

    由质数试除法原理,若 ii 为合数,必存在小于等于 i\sqrt{i} 的质因子,因此试除到 ⌊i⌋\lfloor\sqrt{i}\rfloor 即可完全覆盖。

    复杂度分析

    • 时间复杂度:外层循环执行 n−1n - 1 次,内层试除至多 i\sqrt{i} 次。总时间复杂度为 ∑i=2nO(i)≈O(nn)\sum_{i=2}^n O(\sqrt{i}) \approx O(n\sqrt{n})。当 n=1000n = 1000 时,计算量大约为 3×1043 \times 10^4 次基本操作,运行时间远低于 1 秒。
    • 空间复杂度:O(1)O(1)。

    信息

    ID
    121
    时间
    1000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    2
    已通过
    1
    上传者