1. 判断一个数是不是素数（函数）#

1
#include <iostream>
2
using namespace std;
3

4
bool isPrime(int x) {
5
    // 小于 2 的数一定不是素数
6
    if (x < 2) return false;
7

8
    // 从 2 遍历到 sqrt(x)，只要能整除，就不是素数
9
    for (int i = 2; i * i <= x; i++) {
10
        if (x % i == 0) {
11
            return false;
12
        }
13
    }
14
    // 都不能整除 → 是素数
15
    return true;
16
}

怎么用？#

1
int main() {
2
    int x;
3
    cin >> x;
4
    if (isPrime(x)) {
5
        cout << x << " 是素数";
6
    } else {
7
        cout << x << " 不是素数";
8
    }
9
    return 0;
10
}

2. 求区间 [L, R] 内素数个数（暴力法）#

直接循环每个数，调用上面的函数即可。

1
int main() {
2
    int L, R;
3
    cin >> L >> R;
4

5
    int cnt = 0; // 统计素数个数
6

7
    // 遍历 L ~ R 每个数
8
    for (int i = L; i <= R; i++) {
9
        if (isPrime(i)) {
10
            cnt++;
11
        }
12
    }
13

14
    cout << cnt << endl;
15
    return 0;
16
}

3. 埃氏筛（区间素数统计）#

如果 数字范围很大（比如 1~1e6），暴力会超时，用埃氏筛：

1
#include <iostream>
2
using namespace std;
3

4
const int MAX = 1000005;
5
bool isPrime[MAX];
6

7
// 埃氏筛：把 1~maxn 的素数全部筛出来
8
void sieve(int maxn) {
9
    // 先假设所有数都是素数
10
    for (int i = 0; i <= maxn; i++) isPrime[i] = true;
11
    isPrime[0] = isPrime[1] = false;
12

13
    for (int i = 2; i * i <= maxn; i++) {
14
        if (isPrime[i]) {
15
            // 把 i 的倍数全部标记为非素数
16
            for (int j = i * i; j <= maxn; j += i) {
17
                isPrime[j] = false;
18
            }
19
        }
20
    }
21
}
22

23
int main() {
24
    int L, R;
25
    cin >> L >> R;
26

27
    sieve(R); // 筛到 R 即可
28

29
    int cnt = 0;
30
    for (int i = L; i <= R; i++) {
31
        if (isPrime[i]) cnt++;
32
    }
33

34
    cout << cnt;
35
    return 0;
36
}