C++素数判定完全指南（从零开始掌握高效判断素数的C++算法）

方法一：暴力法（基础版）

最直观的方法是从2开始，逐个检查到 n-1，看是否有能整除 n 的数。如果有，则不是素数。

#include <iostream>using namespace std;bool isPrime(int n) {    if (n <= 1) return false; // 小于等于1不是素数    for (int i = 2; i < n; i++) {        if (n % i == 0) {            return false; // 找到因数，不是素数        }    }    return true; // 没有找到因数，是素数}int main() {    int num;    cout << "请输入一个整数: ";    cin >> num;    if (isPrime(num)) {        cout << num << " 是素数。" << endl;    } else {        cout << num << " 不是素数。" << endl;    }    return 0;}

这种方法简单易懂，但效率很低，时间复杂度为 O(n)。当 n 很大时（比如10⁶以上），程序会变得非常慢。

方法二：优化版（只检查到√n）

数学知识告诉我们：如果一个数 n 有因数，那么至少有一个因数小于或等于 √n。因此，我们只需检查从2到√n之间的数即可。

#include <iostream>#include <cmath> // 用于 sqrt 函数using namespace std;bool isPrime(int n) {    if (n <= 1) return false;    if (n == 2) return true;  // 2 是唯一的偶素数    if (n % 2 == 0) return false; // 排除其他偶数    // 只检查奇数，从3到√n    for (int i = 3; i <= sqrt(n); i += 2) {        if (n % i == 0) {            return false;        }    }    return true;}int main() {    int num;    cout << "请输入一个整数: ";    cin >> num;    if (isPrime(num)) {        cout << num << " 是素数。" << endl;    } else {        cout << num << " 不是素数。" << endl;    }    return 0;}

这个版本的时间复杂度降到了 O(√n)，效率大幅提升！这也是实际开发中最常用的C++判断素数方法。

方法三：埃拉托斯特尼筛法（批量生成素数）

如果你需要找出某个范围内所有的素数（比如1到10000），可以使用著名的“埃拉托斯特尼筛法”（Sieve of Eratosthenes）。这是一种预处理算法，适合多次查询。

#include <iostream>#include <vector>using namespace std;vector<bool> sieve(int n) {    vector<bool> isPrime(n + 1, true);    isPrime[0] = isPrime[1] = false; // 0和1不是素数    for (int i = 2; i * i <= n; i++) {        if (isPrime[i]) {            for (int j = i * i; j <= n; j += i) {                isPrime[j] = false; // 标记i的倍数为非素数            }        }    }    return isPrime;}int main() {    int n = 30;    vector<bool> primes = sieve(n);    cout << "1 到 " << n << " 之间的素数有：";    for (int i = 2; i <= n; i++) {        if (primes[i]) {            cout << i << " ";        }    }    cout << endl;    return 0;}

筛法的时间复杂度为 O(n log log n)，非常适合处理大量数据。虽然内存占用稍高，但在现代计算机上完全可接受。

总结

通过本教程，你已经掌握了三种常见的素数算法：

• 暴力法：适合理解原理，但效率低；
• √n优化法：日常使用推荐，兼顾简洁与效率；
• 埃拉托斯特尼筛法：适合批量处理或频繁查询。

无论你是编程新手还是正在准备面试，这些C++素数判定技巧都值得收藏和练习。动手写一写代码，你会发现素数其实没那么神秘！

提示：在实际项目中，建议使用第二种方法（√n优化法），它在大多数场景下表现最佳。