数

题目

出题人讨厌素数，因为他平翘舌不分。

这天计算机数学下课以后，小J和小R走在去食堂的路上。

小J："刚刚那么多定理都说了一定要在p是奇素数下才成立，你说有多少个奇素数啊。"

小R："……你放过我吧，刚下课，你让我好好吃个饭，那你先告诉我100到1000有多少个奇素数呢？"

小J："……你也没放过我啊。"

小J和小R看起来并不太能完成这个任务，现在想要屏幕前的你来帮助他们计算。

小J和小R会告诉你一个范围（闭区间），请你告诉他们，在这个范围内有多少个奇素数。

输入：两个整数 L 和 R，表示闭区间的左右端点。
输出：一个整数，表示范围内奇素数的数量。

样例1：

2 10

3

样例2：

10 20

4

提示：对于 30% 的数据，保证 L≤R≤100。对于 70% 的数据，保证 L≤R≤10000。对于 100% 的数据，保证 L≤R≤100000。

思路

试除法逐一判断 [L, R] 内每个数是否为素数，统计总数。因为 2 是唯一的偶素数，奇素数 = 所有素数 − 2，所以最后若区间包含 2（即 L ≤ 2 且 R ≥ 2），答案减 1。

#include<bits/stdc++.h>
using namespace std;

// 试除法判断素数
bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    int limit = sqrt(n);
    for (int i = 3; i <= limit; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int L, R;
    cin >> L >> R;

    int count = 0;
    for (int i = L; i <= R; i++) {
        if (isPrime(i)) {
            count++;
        }
    }

    // 如果区间包含 2，则将其从统计结果中减去（因为题目只要求奇素数）
    if (L <= 2 && R >= 2) {
        count--;
    }

    cout << count << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O((R−L+1)·√R)，对区间内每个数试除到其平方根
• 空间复杂度：O(1)

← 返回菜鸟的coding