质数判断算法：从基础到优化的完整指南

1. 项目概述

这道OJ题目看似简单，实则暗藏玄机。作为计算机专业学生必练的基础算法题，"找出质数"考察的远不止循环和判断语句的使用。在实际开发中，质数判断算法广泛应用于密码学、哈希表设计等关键领域。本文将带你从暴力解法入手，逐步优化到筛法实现，并分享我在ACM竞赛中积累的质数判断技巧。

2. 质数判断基础原理

2.1 质数的数学定义

质数（Prime number）指在大于1的自然数中，除了1和它本身外不再有其他因数的数。理解这个定义时需要注意三个关键点：

1. 质数必须大于1（所以1不是质数）
2. 只有两个正因数
3. 必须是自然数（正整数）

2.2 基础判断算法实现

最直观的判断方法就是试除法。对于一个待判断的数n，我们只需要用2到n-1之间的所有整数去试除n，如果都不能整除，则n是质数。用C++实现如下：

cpp复制bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

这个实现虽然正确，但效率极低。时间复杂度是O(n)，当n较大时（比如10^9量级），这个算法几乎无法在合理时间内完成。

3. 算法优化策略

3.1 试除法的优化空间

观察质数的性质可以发现几个优化点：

1. 只需要检查到√n即可：如果n有因数，那么必定有一个因数小于等于√n
2. 可以跳过偶数判断：除了2以外，所有偶数都不是质数
3. 可以预先生成小质数表进行快速判断

优化后的算法实现：

cpp复制bool isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

这个优化将时间复杂度降到了O(√n)，性能提升显著。对于n=10^9的情况，循环次数从10^9次降到了约3万次。

3.2 埃拉托斯特尼筛法

当需要找出一定范围内的所有质数时，筛法（Sieve）效率更高。埃拉托斯特尼筛法的基本思想是：

1. 初始化一个布尔数组isPrime[]，标记所有数为质数
2. 从2开始，将每个质数的倍数标记为非质数
3. 最后仍被标记为质数的就是结果

C++实现示例：

cpp复制vector<bool> sieve(int maxNum) {
    vector<bool> isPrime(maxNum + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= maxNum; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= maxNum; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

筛法的时间复杂度是O(n log log n)，空间复杂度是O(n)。适合需要预处理质数表的场景。

4. 完整解题实现

4.1 题目要求分析

东华OJ-101题通常要求：

• 输入一个整数n（n > 1）
• 输出2到n之间的所有质数
• 每个质数占一行
• 需要考虑时间限制（通常1秒）

4.2 优化后的解决方案

结合上述分析，我们采用筛法实现：

cpp复制#include <iostream>
#include <vector>
using namespace std;

void printPrimes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = 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]) {
            cout << i << endl;
        }
    }
}

int main() {
    int n;
    cin >> n;
    printPrimes(n);
    return 0;
}

4.3 关键点解析

1. 初始化vector时大小设为n+1，因为要包含0到n的所有数
2. 外层循环只需到√n，这是筛法的核心优化
3. 内层循环从i*i开始，因为更小的倍数已经被之前的质数筛掉了
4. 输出时从2开始遍历，避免不必要的判断

5. 性能优化技巧

5.1 内存优化

对于特别大的n（比如10^8），bool数组可能占用过多内存。可以采用位压缩技术：

cpp复制vector<uint8_t> isPrime((n + 7) / 8, 0xFF);  // 每个字节存储8个标志位

void setNotPrime(int num) {
    isPrime[num >> 3] &= ~(1 << (num & 7));
}

bool checkPrime(int num) {
    return isPrime[num >> 3] & (1 << (num & 7));
}

这种方法可以将内存使用减少到原来的1/8。

5.2 分段筛法

当n极大时（比如10^12），无法一次性加载到内存。可以采用分段筛法：

1. 先筛出√n以内的质数
2. 将区间分成若干段，每段大小适合内存
3. 用预筛的质数来筛每一段

5.3 多线程优化

现代CPU多核心，可以将筛法并行化：

• 将区间划分为多个子区间
• 每个线程处理一个子区间
• 注意处理好边界条件

6. 常见问题与调试技巧

6.1 边界条件处理

• n=1时应该无输出
• n=2时只输出2
• 注意数组越界问题（特别是筛法中j的终止条件）

6.2 性能问题排查

如果程序超时，检查：

1. 是否使用了最优算法（筛法优于试除法）
2. 循环终止条件是否正确（i*i<=n而非i<=n）
3. 是否跳过了不必要的判断（如偶数）

6.3 内存问题排查

对于大n，可能出现内存不足。解决方案：

1. 使用位压缩技术
2. 改用分段筛法
3. 在OJ环境中申请更大的栈空间

7. 实际应用场景

质数判断算法在以下领域有重要应用：

1. 密码学：RSA加密算法依赖大质数
2. 哈希算法：质数用于设计哈希函数
3. 随机数生成：质数用于构造伪随机数生成器
4. 算法竞赛：许多题目需要高效的质数判断

8. 扩展学习建议

1. 米勒-拉宾素性测试：概率性质数测试算法，适合极大数的快速判断
2. 线性筛法：可以在O(n)时间内筛出质数，适合需要质数表的场景
3. 质因数分解：基于质数判断的扩展算法
4. 欧拉函数：与质数密切相关的数论函数

9. 个人实战经验

在ACM竞赛中处理质数问题时，我总结了几点经验：

1. 预处理是关键：如果题目允许预处理，先筛出可能用到的质数表

2. 空间换时间：在内存允许的情况下，预计算可以大幅提升运行速度

3. 注意数据范围：不同范围的n适用不同算法

   • n<10^6：普通筛法
   • 10^6<n<10^8：位压缩筛法
   • n>10^8：分段筛法或概率算法

4. 测试用例要全面：特别关注边界值（0,1,2,偶数，大质数等）

最后分享一个实用技巧：在C++中，可以用bitset代替vector来实现筛法，通常会有更好的性能：

cpp复制bitset<10000001> isPrime;  // 声明时大小必须为常量
isPrime.set();  // 全部初始化为1