CC++ & Algorithm

素数与合数的判定

困难7
语言版本：通用
概述：从生活中的房间号码出发，讲解什么是素数、什么是合数，以及如何通过试除判断一个数是否为素数。

从认识素数到筛法：一步步学会判断和批量找出素数

什么是素数和合数？

想象你去一个巨大的酒店，房间从1号开始一直排到很大的号码。你朋友说：“我的房间号很特别，它只能被1和它自己整除，没有别的房间能整除它。” 这样的房间号就是素数（也叫质数）。而像6号房间，不仅1和6能整除它，2和3也能整除它，这样的房间号就是合数。

在我们的数学世界里，大于1的自然数可以被分成两类：素数和合数。

  • 素数：只有两个正因数——1和它本身。例如：2, 3, 5, 7, 11, 13 …
  • 合数：除了1和它本身以外，还有别的正因数。例如：4, 6, 8, 9, 10 …
  • 数字1很特殊，它只有一个因数（1），所以它既不是素数也不是合数。

为什么学习素数很重要？
素数是数论中的“原子”——所有大于1的整数都可以唯一地分解成素数的乘积（算术基本定理）。在编程中，经常需要判断一个数是不是素数，比如密码学里用大素数来加密信息，或者游戏里随机生成素数作为ID。

接下来，我们一步步学习如何用程序判断一个数是不是素数，以及如何快速找出一个范围内的所有素数。

第一部分：试除法——最直接的单个数判断

生活中的例子

假如你要在一个巨大的图书馆里找一本名字只有一个字的书（比如叫“素”）。你可以从第一本书开始挨个查看书名，直到找到那本书或者翻完所有书——这就好比试除法：用从2到n-1的所有数去试除n，看有没有能整除的。

但图书馆有100万本书，一本本翻太慢了。聪明的管理员告诉你：“书的编号都是整数，你只需要检查前1000个书架，因为如果后面的架子上有那本书，前面的某个架子上也一定有一本和它成对的书。” 这就是只检查到平方根的道理。

数学原理

对于一个大于1的自然数 nn：

  • 如果 nn 是合数，那么它一定有一个因子 dd 满足 2≤d≤n2 \le d \le \sqrt{n}。因为如果所有因子都大于 n\sqrt{n}，那么两个因子相乘就会大于 nn，矛盾。
  • 因此，我们只需要用从2到 n\sqrt{n} 的整数去试除 nn，就可以判断它是否为素数。

优化技巧

  1. 只试除到 n\sqrt{n}：减少试除次数，复杂度从 O(n)O(n) 降到 O(n)O(\sqrt{n})。
  2. 先排除2和所有偶数：除了2以外，所有偶数都不是素数。判断时先检查2，然后只试除奇数。
  3. 6k±1规则：所有大于3的素数都可以写成 6k±16k \pm 1 的形式。因此试除时只检查形如 6k±16k \pm 1 的数，进一步减少到约 n/3\sqrt{n}/3 次。

常见错误（新手容易犯）

  • 忘记处理 n <= 1 的情况（1不是素数也不是合数，应返回 false）。
  • 忘记排除偶数（如把 4 误判为素数）。
  • 循环条件写成 i < sqrt(n) 而不是 i <= sqrt(n)（比如 n=4，sqrt(4)=2，应该检查2，但写成 < 会漏掉）。
  • 使用 sqrt 时把结果转成整数，要注意浮点数精度问题，可以加一个小数或直接用 i*i <= n 来避免。

完整代码示例（C++ + Python）

C++ 实现（6k±1优化）

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
    // 处理小情况
    if (n <= 1) return false;   // 1和负数不是素数
    if (n == 2 || n == 3) return true;  // 2和3是素数
    if (n % 2 == 0 || n % 3 == 0) return false; // 能被2或3整除则不是

    // 从5开始，步长6，检查i和i+2（对应6k±1）
    int limit = sqrt(n);  // 平方根
    for (int i = 5; i <= limit; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false; // 找到了因子
        }
    }
    return true; // 没有找到因子，是素数
}

int main() {
    int num;
    cout << "请输入一个正整数: ";
    cin >> num;
    if (isPrime(num)) {
        cout << num << " 是素数" << endl;
    } else {
        cout << num << " 不是素数" << endl;
    }
    return 0;
}

Python 实现（6k±1优化）

import math

def is_prime(n):
    # 处理小情况
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    # 从5开始，步长6，检查i和i+2
    limit = int(math.sqrt(n))
    i = 5
    while i <= limit:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

# 主程序
num = int(input("请输入一个正整数: "))
if is_prime(num):
    print(num, "是素数")
else:
    print(num, "不是素数")

第二部分：埃拉托斯特尼筛法（埃氏筛）——批量找出小范围内的所有素数

生活中的例子

想象你要从一大袋混有石子的面粉中筛出面粉，留下石子。你有一把筛子，筛孔大小恰好能让面粉颗粒通过，而石子通不过。你摇晃筛子，面粉陆续掉下去，最后筛子上只剩下石子。

埃拉托斯特尼筛法就像这个筛子：它从2开始，把所有2的倍数（除了2本身）标记为“合数”，然后下一个未被标记的数（3）也是素数，再筛掉所有3的倍数……这样反复，最后剩下的没有被标记的数就是素数。

你也可以把它想象成“发卷子”：老师有一沓从1到N的试卷，她先拿过2号卷子，把它当做优秀作文（素数），然后把所有编号是2的倍数的试卷都挑出来放到“合数”堆；接着看下一个还在手中的卷子3号，同样作为优秀作文，然后挑出所有编号是3的倍数的卷子；不断重复，直到把所有卷子处理完毕。最后手中剩下的试卷就是素数。

数学原理

给定一个上限 nn，找出所有小于等于 nn 的素数：

  1. 创建一个布尔数组 is_prime[0..n]，初始所有值设为 true（假定都是素数）。
  2. 将0和1标记为 false，因为它们不是素数。
  3. 从2开始，如果当前数 i 是素数（即 is_prime[i] == true），则将所有 i 的倍数（从 i2i^2 开始，因为更小的倍数已经被更小的素数筛过了）标记为合数（false）。
  4. 继续下一个 i，直到 i2>ni^2 > n。

为什么从 i2i^2 开始？ 因为对于 ii 的倍数 k⋅ik \cdot i（k<ik < i），它已经在处理素数 kk 时被标记过了，从 i2i^2 开始可以避免重复标记。

复杂度

  • 时间复杂度：O(nlog⁡log⁡n)O(n \log \log n)
  • 空间复杂度：O(n)O(n)

常见错误

  • 忘记初始化 is_prime[0] 和 is_prime[1] 为 false。
  • 内层循环从 2*i 开始而不是 i*i，导致大量重复标记。
  • 循环条件写成 i <= n 而不是 i*i <= n，增加了不必要的遍历。
  • 数组越界：当 i*i 可能超过 n 时，需要先检查 i*i <= n 再进入循环。

完整代码示例

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

// 埃氏筛，返回小于等于n的所有素数
vector<int> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true); // 布尔数组，true表示暂时是素数
    vector<int> primes;                // 存储素数结果

    // 0和1不是素数
    if (n >= 0) isPrime[0] = false;
    if (n >= 1) isPrime[1] = false;

    // 从2开始筛
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {                    // 如果i是素数
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;          // 标记为合数
            }
        }
    }

    // 收集所有素数
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

int main() {
    int n;
    cout << "请输入上限n: ";
    cin >> n;
    vector<int> primes = sieveOfEratosthenes(n);
    cout << n << "以内的素数有 " << primes.size() << " 个，它们是：" << endl;
    for (int p : primes) {
        cout << p << " ";
    }
    cout << endl;
    return 0;
}

Python 实现

def sieve_of_eratosthenes(n):
    # 创建布尔数组，长度为n+1，初始均为True
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0和1不是素数

    i = 2
    while i * i <= n:
        if is_prime[i]:                     # 如果i是素数
            for j in range(i * i, n + 1, i):
                is_prime[j] = False         # 标记为合数
        i += 1

    # 收集所有素数
    primes = [i for i in range(2, n + 1) if is_prime[i]]
    return primes

# 主程序
n = int(input("请输入上限n: "))
primes = sieve_of_eratosthenes(n)
print(f"{n}以内的素数有 {len(primes)} 个，它们是：")
print(primes)

第三部分：线性筛法（欧拉筛）——更高效的批量筛法

生活中的例子

你在学校发传单，每个同学有一份传单要发，但你不想重复发：比如张三已经给李四发了传单，王五就不必再给李四发了。在埃氏筛中，一个合数（比如30）会被多个素数（2、3、5）反复标记，就像多个同学给同一个人发传单一样，是一种浪费。

线性筛法（也叫欧拉筛）通过精心设计，让每个合数只被它的最小质因子标记一次，从而把复杂度降到 O(n)O(n)，就像每个同学只由他的“班长”负责发传单，不会重复。

数学原理

线性筛维护一个素数列表 primes，以及一个布尔数组 is_prime。对于每个整数 i 从2到 nn：

  1. 如果 i 是素数（即 is_prime[i] 为真），则把 i 加入 primes 列表。
  2. 然后遍历 primes 中的每个素数 p（从小到大）：
    • 标记 i * p 为合数（即 is_prime[i * p] = false）。
    • 如果 i 能被 p 整除，则跳出循环（这是关键！）。

为什么跳出？ 因为如果 i % p == 0，说明 p 是 i 的最小质因子，那么对于更大的素数 q > p，i * q 的最小质因子仍然是 p，它将来会在处理另一个更大的 i' 时被标记（i' = (i * q) / p），所以这里应该停止，避免重复。

这样每个合数恰好被其最小质因子标记一次，总标记次数等于合数个数，时间复杂度为 O(n)O(n)。

示例过程（n=30）

i=2: 是素数 → primes=[2]; 标记2*2=4; i%2==0 跳出
i=3: 是素数 → primes=[2,3]; 标记3*2=6, 3%2!=0; 标记3*3=9, 3%3==0 跳出
i=4: 不是素数; 标记4*2=8; 4%2==0 跳出
i=5: 是素数 → primes=[2,3,5]; 标记5*2=10, 5%2!=0; 标记5*3=15, 5%3!=0; 标记5*5=25, 5%5==0 跳出
...

可以看到每个合数只被标记一次。

常见错误

  • 忘记写 break 条件，导致重复标记，退化为埃氏筛的复杂度。
  • 内层循环的边界 i * p <= n 未写，导致数组越界。
  • 在 Python 中遍历 primes 的同时向 primes 添加元素（当 i 是素数时，先添加，再遍历）。Python 的 for p in primes 在迭代器创建后，若列表长度变化，可能会产生未定义行为。但通常线性筛代码中，内层循环是在添加新素数之后立即开始的，而内层循环本身不会修改 primes，所以安全。不过更严谨的做法是用索引访问。

完整代码示例

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

// 线性筛（欧拉筛），返回小于等于n的所有素数
vector<int> linearSieve(int n) {
    vector<bool> isPrime(n + 1, true); // 布尔数组，true表示暂定为素数
    vector<int> primes;                // 存储素数

    if (n >= 0) isPrime[0] = false;
    if (n >= 1) isPrime[1] = false;

    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i); // i是素数，加入列表
        }
        // 遍历当前所有素数，标记合数 i * primes[j]
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            isPrime[i * primes[j]] = false; // 标记合数
            if (i % primes[j] == 0) {
                break; // 关键：如果primes[j]整除i，则跳出循环
            }
        }
    }
    return primes;
}

int main() {
    int n;
    cout << "请输入上限n: ";
    cin >> n;
    vector<int> primes = linearSieve(n);
    cout << n << "以内的素数有 " << primes.size() << " 个。" << endl;
    // 可打印素数列表，但n很大时注释掉
    // for (int p : primes) cout << p << " ";
    return 0;
}

Python 实现

def linear_sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    primes = []

    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)               # i是素数，加入列表
        # 遍历所有素数，标记合数 i * p
        for p in primes:
            if i * p > n:
                break
            is_prime[i * p] = False        # 标记合数
            if i % p == 0:                 # 关键条件
                break
    return primes

# 主程序
n = int(input("请输入上限n: "))
primes = linear_sieve(n)
print(f"{n}以内的素数有 {len(primes)} 个。")

第四部分：区间筛法——处理大范围中的小区间

生活中的例子

假设你要在一个巨大的体育馆里找一个丢失的小球，体育馆有10万个座位，但小球只可能落在其中某一排（比如第1万排到第1万零1百排）的座位上。你不需要检查整个体育馆，只需要检查这一小段座位。

区间筛法就是类似的道理：如果我们需要找出一个很大的区间 [L, R) 内的所有素数，但区间长度 R-L 不大（例如 10610^6 以内），而 R 可能达到 101210^{12} 以上，我们不能创建一个从0到R的巨大数组（内存不够）。我们可以先找出所有小于等于 sqrt(R) 的素数（用普通筛法），然后用这些素数去“筛”这个小区间，就像用一个小的检查表去扫描特定的一排座位。

数学原理

  1. 基底素数：先用埃氏筛或线性筛找出 [2,R][2, \sqrt{R}] 中的所有素数（最多约 10610^6 个）。
  2. 区间数组：创建一个布尔数组 is_prime_seg，长度为 R - L，初始为 true，表示区间内的每个数暂时被认为是素数。
  3. 筛选：对于每个基底素数 p，在区间 [L, R) 中找出 p 的第一个倍数（至少是 p 本身），然后标记该倍数为合数，并继续标记所有 p 的倍数，直到超出区间。
    • 第一个要标记的合数 = max(p * p, ceil(L / p) * p)。
    • 注意：如果 p 本身在区间内，且 p * p > R，则不会标记它，它会被保留为素数。
  4. 收集结果：最后数组中为 true 的位置对应的数（且大于1）就是区间内的素数。

复杂度

  • 筛基底素数：O(Rlog⁡log⁡R)O(\sqrt{R} \log \log \sqrt{R})
  • 标记区间倍数：约 (R−L)⋅∑p≤R1p≈(R−L)⋅log⁡log⁡R(R-L) \cdot \sum_{p \le \sqrt{R}} \frac{1}{p} \approx (R-L) \cdot \log \log \sqrt{R}
  • 总复杂度近似 O((R−L)log⁡log⁡R+R)O((R-L) \log \log \sqrt{R} + \sqrt{R})，空间 O(R+(R−L))O(\sqrt{R} + (R-L))。

常见错误

  • 当 L=1 时，区间内的1会被误判为素数（需要最后排除 num < 2）。
  • 计算第一个倍数时，使用 ceil(L/p) 时注意整数除法，正确写法是 ((L + p - 1) // p) * p。
  • 基底素数要包含所有 ≤ sqrt(R) 的素数，包括可能等于 sqrt(R) 的素数。
  • 如果 p 本身在区间内且 p * p <= R，那么 max(p*p, ...) 中 p*p 可能大于等于第一个倍数，但不会标记 p 本身，因为 p 不是倍数（从 p*p 开始）。但如果 p 在区间内且 p < L，则 p 不在区间内，无需担心。
  • 注意数组索引偏移： is_prime_seg[j - L]。

完整代码示例

C++ 实现

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 埃氏筛，返回[2, n]内的所有素数
vector<long long> getPrimes(long long n) {
    vector<bool> isPrime(n + 1, true);
    vector<long long> primes;
    if (n >= 0) isPrime[0] = false;
    if (n >= 1) isPrime[1] = false;
    for (long long i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            for (long long j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (long long i = 2; i <= n; ++i) {
        if (isPrime[i]) primes.push_back(i);
    }
    return primes;
}

// 区间筛，返回区间[L, R)内的所有素数
vector<long long> segmentSieve(long long L, long long R) {
    long long limit = sqrt(R) + 1;                      // 基底素数的上界
    vector<long long> basePrimes = getPrimes(limit);    // 基底素数列表

    long long segLen = R - L;                           // 区间长度
    vector<bool> isPrimeSeg(segLen, true);              // 区间布尔数组，true表示暂时是素数

    for (long long p : basePrimes) {
        // 区间内第一个p的倍数，并且至少从p*p开始（避免重复标记）
        long long start = max(p * p, ((L + p - 1) / p) * p);
        // 标记所有p的倍数
        for (long long j = start; j < R; j += p) {
            isPrimeSeg[j - L] = false;
        }
    }

    vector<long long> ans;
    for (long long i = 0; i < segLen; ++i) {
        if (isPrimeSeg[i]) {
            long long num = L + i;
            if (num >= 2) {        // 素数必须大于1
                ans.push_back(num);
            }
        }
    }
    return ans;
}

int main() {
    long long L, R;
    cout << "请输入区间的左边界L和右边界R（左闭右开，如 100 200）: ";
    cin >> L >> R;
    vector<long long> primes = segmentSieve(L, R);
    cout << "区间[" << L << ", " << R << ")内的素数共 " << primes.size() << " 个:" << endl;
    for (long long p : primes) {
        cout << p << " ";
    }
    cout << endl;
    return 0;
}

Python 实现

import math

def get_primes(n):
    """返回[2, n]内的素数列表"""
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(math.isqrt(n)) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return [i for i in range(2, n + 1) if is_prime[i]]

def segment_sieve(L, R):
    """返回区间[L, R)内的素数列表"""
    limit = int(math.isqrt(R)) + 1          # 基底素数的上界
    base_primes = get_primes(limit)         # 基底素数

    seg_len = R - L
    is_prime_seg = [True] * seg_len         # 区间布尔数组

    for p in base_primes:
        # 区间内第一个p的倍数（至少从p*p开始）
        first = max(p * p, ((L + p - 1) // p) * p)
        # 标记倍数
        for j in range(first, R, p):
            is_prime_seg[j - L] = False

    # 收集结果，排除1
    ans = []
    for i in range(seg_len):
        if is_prime_seg[i]:
            num = L + i
            if num >= 2:
                ans.append(num)
    return ans

# 主程序
L = int(input("请输入区间的左边界L: "))
R = int(input("请输入区间的右边界R (不包含R): "))
primes = segment_sieve(L, R)
print(f"区间[{L}, {R})内的素数共 {len(primes)} 个:")
print(primes)

第五部分：素数计数与分布——统计素数个数

生活中的例子

假如你是一个统计员，需要统计一个城市里有多少人姓“张”。如果你有一个完整的电话簿，你可以一个个数，但电话簿有100万页，数起来太费劲。这时候有人告诉你了一个经验公式：姓张的人数大约等于城市总人口乘以0.08。虽然不完全精确，但可以快速估计。

素数计数也有类似的“经验公式”，叫做素数定理，可以估算小于某个数的素数有多少个。比如，小于100万大约有78498个素数，而根据公式估算大约是72382个，误差不算太大。

对于小范围的准确计数，我们可以用筛法先筛出所有素数再数个数。对于大范围，则用近似估计。

数学原理

素数计数函数 π(x)\pi(x)：表示不大于 xx 的素数个数。例如 π(10)=4\pi(10)=4（2,3,5,7），π(100)=25\pi(100)=25。

素数定理（Prime Number Theorem）：

π(x)∼xln⁡x(x→∞)\pi(x) \sim \frac{x}{\ln x} \quad (x \to \infty)

更精确的近似是 π(x)≈Li(x)=∫2xdtln⁡t\pi(x) \approx \text{Li}(x) = \int_2^x \frac{dt}{\ln t}，但 x/ln⁡xx/\ln x 已经足够直观。

例如：

  • x=103x=10^3：π(1000)=168\pi(1000)=168，x/ln⁡x≈144.8x/\ln x \approx 144.8
  • x=106x=10^6：π(106)=78498\pi(10^6)=78498，x/ln⁡x≈72382x/\ln x \approx 72382
  • x=109x=10^9：π(109)≈50847534\pi(10^9)\approx 50847534，x/ln⁡x≈48254942x/\ln x \approx 48254942

随着 xx 增大，相对误差逐渐减小。

分布特点：素数越往大越稀疏。大约每 ln⁡x\ln x 个连续自然数中才有一个素数。例如在 10910^9 附近，平均每21个数中有一个素数；而在100以内，平均每4个数就有一个素数。

小范围精确计算：对于 x≤107x \le 10^7，可以用埃氏筛或线性筛一次性得到所有素数，然后直接统计个数。也可以在筛法过程中计数，避免二次遍历。

完整代码示例（计数）

C++ 实现（在筛法中直接计数）

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 埃氏筛计数，返回不大于n的素数个数
int primeCount(int n) {
    if (n < 2) return 0;
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    int count = n - 1; // 初始假设除了0和1都是素数
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                if (isPrime[j]) {
                    isPrime[j] = false;
                    count--; // 每发现一个合数就减少计数
                }
            }
        }
    }
    return count;
}

int main() {
    int n;
    cout << "请输入n: ";
    cin >> n;
    cout << "小于等于" << n << "的素数个数是: " << primeCount(n) << endl;
    // 近似公式
    cout << "近似公式 x/ln(x) ≈ " << n / log(n) << endl;
    return 0;
}

Python 实现

import math

def prime_count(n):
    if n < 2:
        return 0
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    count = n - 1  # 初始假设除了0和1都是素数
    for i in range(2, int(math.isqrt(n)) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                if is_prime[j]:
                    is_prime[j] = False
                    count -= 1
    return count

# 主程序
n = int(input("请输入n: "))
print(f"小于等于{n}的素数个数是: {prime_count(n)}")
print(f"近似公式 x/ln(x) ≈ {n / math.log(n):.2f}")

综合示例：一个多功能的素数工具程序

下面给出一个整合了“单个数判断”、“埃氏筛输出所有素数”、“区间筛输出区间素数”和“素数计数”的程序（C++版本）。你可以根据需要选择功能。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

// 试除法判断单个数是否为素数（6k±1优化）
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    int limit = sqrt(n);
    for (int i = 5; i <= limit; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

// 埃氏筛，返回[2, n]内所有素数
vector<int> sieveAll(int n) {
    vector<bool> isPrime(n + 1, true);
    vector<int> primes;
    if (n >= 0) isPrime[0] = false;
    if (n >= 1) isPrime[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) primes.push_back(i);
    }
    return primes;
}

// 区间筛，返回[L, R)内素数
vector<long long> sieveSegment(long long L, long long R) {
    long long limit = sqrt(R) + 1;
    vector<long long> base = sieveAll(limit); // 复用埃氏筛（但sieveAll返回int，注意转换）
    // 这里为了简洁，重新写一个针对long long的基底素数函数，但此处直接用sieveAll转换
    vector<long long> basePrimes(base.begin(), base.end());

    long long segLen = R - L;
    vector<bool> isPrimeSeg(segLen, true);
    for (long long p : basePrimes) {
        long long start = max(p * p, ((L + p - 1) / p) * p);
        for (long long j = start; j < R; j += p) {
            isPrimeSeg[j - L] = false;
        }
    }
    vector<long long> ans;
    for (long long i = 0; i < segLen; ++i) {
        if (isPrimeSeg[i]) {
            long long num = L + i;
            if (num >= 2) ans.push_back(num);
        }
    }
    return ans;
}

// 素数计数（埃氏筛过程中计数）
int primeCount(int n) {
    if (n < 2) return 0;
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    int count = n - 1;
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                if (isPrime[j]) {
                    isPrime[j] = false;
                    count--;
                }
            }
        }
    }
    return count;
}

int main() {
    cout << "素数工具（C++版）" << endl;
    cout << "1. 判断单个数是否为素数" << endl;
    cout << "2. 输出[2, n]内所有素数" << endl;
    cout << "3. 输出区间[L, R)内素数" << endl;
    cout << "4. 统计[2, n]内素数个数" << endl;
    cout << "请选择功能 (1-4): ";
    int choice;
    cin >> choice;
    if (choice == 1) {
        int x;
        cout << "请输入正整数: ";
        cin >> x;
        cout << (isPrime(x) ? "是素数" : "不是素数") << endl;
    } else if (choice == 2) {
        int n;
        cout << "请输入n: ";
        cin >> n;
        vector<int> primes = sieveAll(n);
        cout << "素数有 " << primes.size() << " 个: ";
        for (int p : primes) cout << p << " ";
        cout << endl;
    } else if (choice == 3) {
        long long L, R;
        cout << "请输入L和R（左闭右开）: ";
        cin >> L >> R;
        vector<long long> primes = sieveSegment(L, R);
        cout << "区间素数有 " << primes.size() << " 个: ";
        for (long long p : primes) cout << p << " ";
        cout << endl;
    } else if (choice == 4) {
        int n;
        cout << "请输入n: ";
        cin >> n;
        cout << "素数个数: " << primeCount(n) << endl;
        cout << "近似公式 x/lnx ≈ " << n / log(n) << endl;
    } else {
        cout << "无效选择" << endl;
    }
    return 0;
}

相关指引

学完了这些基础，你可以继续探索以下方向：

  • 米勒-拉宾素性测试：用于快速判断大数（例如几百位）是否为素数，是一种概率算法，常用于密码学。
  • Meissel-Lehmer 算法：可以在 O(x2/3)O(x^{2/3}) 时间内计算 π(x)\pi(x) 对于 x=1012x=10^{12} 甚至更大。
  • 数论函数：线性筛除了求素数，还可以顺便求出每个数的最小质因子、欧拉函数 φ\varphi、莫比乌斯函数 μ\mu 等，是解决数论问题的利器。
  • 素数在密码学中的应用：RSA 加密、Diffie-Hellman 密钥交换等都依赖大素数的生成和判定。

总结：

  • 判断单个素数用试除法，优化到 n\sqrt{n} 和 6k±1 就足够快。
  • 批量找出小范围素数用埃氏筛（简单）或线性筛（更快）。
  • 大范围中的小区间用区间筛。
  • 统计素数个数可用筛法直接计数，或借助素数定理做近似估计。

希望这篇文章能帮你从零开始掌握素数的判断与筛法，并激发你继续深入学习数论算法的兴趣！

例题精讲

1单选题

关于整数1，以下说法正确的是？

A1是素数
B1是合数
C1既不是素数也不是合数
D1既是素数又是合数
2判断题

2是最小的素数。

3填空题
以下函数用于判断整数n是否为素数，请补全循环条件（使用试除法优化）。

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; ___; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
4单选题

以下关于合数的描述，正确的是？

A合数有且只有两个正因数
B合数除了1和它本身之外还有别的正因数
C合数只有1和它本身两个因数
D合数没有正因数
5判断题

如果一个整数可以被2整除，那么它一定是合数。