【LeetCode-C】Primary

在C++中高效判断质数需要结合数学规律和算法优化。以下是几种常用的优化方法及其实现思路：

基础优化：试除法与平方根限制

核心原理
若一个数不是质数，其必定有一个因子小于等于其平方根。因此只需遍历到 sqrt(n) 即可。

代码实现

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

优化点：用 i * i <= n 替代 i <= sqrt(n)，避免浮点运算和函数调用开销。

进阶优化：跳过偶数与6的倍数规律

排除偶数和3的倍数
• 除了2和3，所有质数都形如 6k ± 1（k为整数）。 • 先判断是否被2或3整除，然后从5开始以6为步长遍历。

代码实现

bool isPrimeOptimized(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;  // 2和3是质数
    if (n % 2 == 0 || n % 3 == 0) return false;
    // 检查形如6k ± 1的数
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) 
            return false;
    }
    return true;
}

优势：减少约2/3的循环次数。

适用场景优化：筛法预处理

埃拉托斯特尼筛法（Sieve of Eratosthenes）
• 若需频繁判断某个范围内的数是否为质数，可预先生成布尔数组标记质数。 • 时间复杂度：O(n log log n)，空间复杂度：O(n)。

代码片段

std::vector<bool> sieve(int max) {
    std::vector<bool> prime(max + 1, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i * i <= max; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= max; j += i)
                prime[j] = false;
        }
    }
    return prime;
}

适用场景：需要多次查询某个范围内的质数时效率更高。

极端优化：结合位运算与预计算

位运算加速
• 使用位掩码或位操作代替布尔数组，减少内存占用。
预计算质数表
• 提前生成小质数表（如小于100的质数），先检查是否能被这些小质数整除。 • 例如：预存 {2, 3, 5, 7, 11, 13}，快速排除大部分合数。

性能对比与选择建议

方法	时间复杂度	适用场景
基础试除法	O(√n)	单次查询、小数值判断
6k±1优化法	O(√n / 3)	高频单次查询、大数值判断
埃拉托斯特尼筛法	O(n log log n)	范围查询、多次数判断

总结

• 单次判断：优先使用基于6k ±1规律的试除法。 • 范围查询：使用筛法预处理。 • 极端性能需求：结合位运算和预计算优化。

通过数学规律减少不必要的循环次数是提升效率的核心思路。实际应用中需根据具体场景选择最合适的算法。