C++如何判断一个数是素数_C++质数判断的高效算法实现

admin 百科 2025-12-12 11

判断素数的高效方法是检查2到√n间的因子。基础优化：n

C++如何判断一个数是素数_C++质数判断的高效算法实现-第1张图片-佛山资讯网

判断一个数是否为素数（质数）是C++编程中的常见问题。素数是指大于1且只能被1和自身整除的自然数。最简单的实现方式是从2遍历到n-1，但效率极低。下面介绍几种高效且实用的C++实现方法。

基础优化：只检查到√n

一个合数必然有一个小于或等于其平方根的因子。因此，我们只需检查从2到√n之间的所有数即可。

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;
}

登录后复制

这个版本跳过了所有偶数（除了2），减少了约一半的循环次数，适用于中等大小的数（如n

进一步优化：6k±1 法则

除了2和3，所有素数都可以表示为6k±1的形式。利用这一点可以大幅减少判断次数。

立即学习“C++免费学习笔记（深入）”；

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

登录后复制

该方法先排除能被2或3整除的数，然后从5开始，每次检查i和i+2（即6k-1和6k+1），步长为6。在实际测试中比前一种更快。

标签： c++ 常见问题质数 c++编程