C++如何判断一个数是否为素数？C++质数判断算法优化技巧有哪些

素数也叫质数，是指大于1的自然数中，除了1和它本身之外没有其他正因数的数。在C++中实现素数判断时，基础方法存在冗余计算，通过合理的优化可以显著提升判断效率，下面逐步介绍不同场景下的实现方案。

基础素数判断方法

最直观的思路是从2开始遍历到目标数减1，检查是否存在能整除目标数的因数，如果存在则不是素数，否则是素数。需要注意小于等于1的数都不属于素数。

#include <iostream>
using namespace std;

// 基础素数判断函数
bool isPrimeBasic(int n) {
    // 小于等于1的数不是素数
    if (n <= 1) {
        return false;
    }
    // 遍历2到n-1，检查是否有因数
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

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

平方根优化技巧

基础方法中遍历到n-1存在很多冗余计算，因为如果一个数n有大于其平方根的因数，那么必然有小于其平方根的对应因数。因此只需要遍历到sqrt(n)即可，能大幅减少循环次数。

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

// 平方根优化后的素数判断函数
bool isPrimeSqrt(int n) {
    if (n <= 1) {
        return false;
    }
    // 只需要遍历到sqrt(n)，i*i <= n 避免重复计算平方根
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

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

偶数预处理优化

除了2之外的所有偶数都不是素数，因此可以先判断目标数是否为偶数，如果是偶数直接返回结果，减少后续的循环判断。同时遍历因数时只需要检查奇数即可，因为偶数不可能整除奇数。

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

// 偶数预处理优化后的素数判断函数
bool isPrimeEvenOpt(int n) {
    if (n <= 1) {
        return false;
    }
    // 2是唯一的偶素数
    if (n == 2) {
        return true;
    }
    // 其他偶数都不是素数
    if (n % 2 == 0) {
        return false;
    }
    // 只需要遍历奇数，从3开始，步长为2
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

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

不同方法效率对比

三种方法的循环次数差异明显，以下是判断大数值时的效率对比参考：

注意事项

• 输入数值为负数或0、1时，直接返回非素数结果，避免无效计算
• 使用i*i <= n代替i <= sqrt(n)可以避免每次循环都调用平方根函数，减少性能损耗
• 如果需求是频繁判断多个素数，可以进一步使用埃拉托斯特尼筛法等批量判断方案，效率更高

C++prime_numberalgorithm_optimizationloop_control修改时间：2026-06-13 21:03:14