C++ 实例 – 判断素数（长文解析）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

素数（Prime Number）是数学中的一个重要概念，它在密码学、算法设计等领域有着广泛的应用。判断一个数是否为素数是编程中常见的基础问题，而C++作为一门高效且功能强大的编程语言，自然成为实现这一功能的热门选择。本文将通过 C++实例 逐步讲解如何编写素数判断程序，从基础到优化，结合代码示例和直观的比喻，帮助编程初学者和中级开发者深入理解这一算法的核心思想。

什么是素数？

素数是指大于1的自然数中，除了1和它本身外，不能被其他自然数整除的数。例如，2、3、5、7都是素数，而4（可被2整除）、6（可被2或3整除）则不是。素数的这一特性类似于“数学世界中的原子”，无法被进一步分解为更小的自然数因数。

在编程中，判断素数的核心逻辑是：检查一个数是否能被除1和自身之外的其他数整除。接下来，我们将通过代码实现这一逻辑。

实例1：基础版素数判断

算法思路

最直观的方法是遍历从2到该数（n）减1的所有整数，逐个检查是否能整除n。如果存在能整除的数，则n不是素数；否则是素数。

代码示例

#include <iostream>  
using namespace std;  

bool is_prime(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 (is_prime(num)) {  
        cout << num << " 是素数。" << endl;  
    } else {  
        cout << num << " 不是素数。" << endl;  
    }  
    return 0;  
}  

代码解析

1. 函数 is_prime：
   • 输入参数 n，返回布尔值（true表示素数，false表示非素数）。
   • 如果 n ≤ 1，直接返回 false（因素数定义要求大于1）。
   • 使用循环从2遍历到 n-1，检查每个数是否能整除 n。
   • 时间复杂度：O(n)，当n较大时，效率较低。

优化思考

例如，判断100是否为素数时，遍历到5（即√100=10的中间值）后，如果未找到因数，就可以提前终止循环。这是因为：

数学定理：如果n有一个大于√n的因数d，那么它必然有一个小于√n的对应因数（n/d）。因此，只需检查到√n即可。

实例2：平方根优化

算法改进

通过数学定理，将循环上限从 n-1 优化为 √n。此时，当找到第一个因数时即可直接返回结果。

代码示例

#include <iostream>  
#include <cmath> // 包含sqrt函数  
using namespace std;  

bool is_prime_optimized(int n) {  
    if (n <= 1) return false;  
    if (n == 2) return true; // 2是唯一偶素数  
    if (n % 2 == 0) return false; // 排除偶数  

    int sqrt_n = sqrt(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 (is_prime_optimized(num)) {  
        cout << num << " 是素数。" << endl;  
    } else {  
        cout << num << " 不是素数。" << endl;  
    }  
    return 0;  
}  

代码解析

1. 优化点：
   • 提前排除偶数：若n是偶数（且不等于2），直接返回 false。
   • 循环步长为2：从3开始，每次递增2，仅检查奇数因数。
   • 循环上限为√n：通过 sqrt(n) 函数计算平方根，减少循环次数。
2. 时间复杂度：O(√n)，效率显著提升。例如，判断10000时，原版需循环9998次，优化后仅需约50次。

实例3：埃拉托斯特尼筛法（高级优化）

筛法原理

埃拉托斯特尼筛法是一种高效的素数生成算法，通过“筛掉”非素数来保留素数。其核心思想是：

1. 初始化一个布尔数组 is_prime，初始值为 true。
2. 从最小的素数2开始，将它的倍数标记为 false（非素数）。
3. 移动到下一个未被标记的数（即素数），重复步骤2。
4. 最终，数组中仍为 true 的位置即为素数。

适用场景

当需要判断大量连续数的素性时（如生成1到N的所有素数），筛法的效率远高于逐个判断。

代码示例

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

vector<bool> sieve_of_eratosthenes(int n) {  
    vector<bool> is_prime(n + 1, true); // 默认所有数为素数  
    is_prime[0] = is_prime[1] = false; // 0和1不是素数  

    for (int i = 2; i * i <= n; i++) {  
        if (is_prime[i]) { // 如果i是素数  
            for (int j = i * i; j <= n; j += i) {  
                is_prime[j] = false; // 筛掉i的倍数  
            }  
        }  
    }  
    return is_prime;  
}  

int main() {  
    int max_num;  
    cout << "请输入最大范围：";  
    cin >> max_num;  

    vector<bool> primes = sieve_of_eratosthenes(max_num);  

    cout << "素数列表：" << endl;  
    for (int i = 2; i <= max_num; i++) {  
        if (primes[i]) {  
            cout << i << " ";  
        }  
    }  
    cout << endl;  
    return 0;  
}  

代码解析

1. 时间复杂度：O(n log log n)，适用于大规模数据。
2. 关键点：
   • 从 i*i 开始筛除倍数，因为更小的倍数已经被之前的素数处理过。
   • 使用 vector<bool> 优化空间，但需注意其特性（如可能以位存储）。

实际案例：综合应用

场景：输入一个数，输出其是否为素数及所有因数

通过结合基础判断与因数列举，可以更直观地理解素数的特性。

代码示例

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

vector<int> get_factors(int n) {  
    vector<int> factors;  
    for (int i = 1; i <= n; i++) {  
        if (n % i == 0) {  
            factors.push_back(i);  
        }  
    }  
    return factors;  
}  

int main() {  
    int num;  
    cout << "请输入一个整数：";  
    cin >> num;  

    if (num <= 1) {  
        cout << "输入的数小于等于1，不是素数。" << endl;  
        return 0;  
    }  

    bool is_prime = true;  
    vector<int> factors = get_factors(num);  
    for (int i = 2; i < factors.size(); i++) {  
        if (factors[i] != num) {  
            is_prime = false;  
            break;  
        }  
    }  

    cout << num << " 的因数有：" << endl;  
    for (int factor : factors) {  
        cout << factor << " ";  
    }  
    cout << endl;  

    if (is_prime) {  
        cout << num << " 是素数。" << endl;  
    } else {  
        cout << num << " 不是素数。" << endl;  
    }  
    return 0;  
}  

输出示例

请输入一个整数：28  
28 的因数有：  
1 2 4 7 14 28  
28 不是素数。  

常见问题解答

Q1：为什么判断到√n即可？

假设n有一个因数d，且d > √n，那么另一个因数必然是n/d，显然n/d < √n。因此，若没有小于等于√n的因数，则n必然是素数。

Q2：如何处理输入负数或0？

素数定义中要求数必须大于1，因此程序应直接返回“非素数”或提示用户输入错误。

Q3：哪些场景适合使用筛法？

当需要批量判断多个数的素性时（如生成1~10000的所有素数），筛法的效率远高于逐个判断。

结论

本文通过三个 C++实例 展示了判断素数的多种方法，从基础的遍历法到高效的筛法，逐步优化了算法的时间复杂度。对于编程初学者，建议从基础代码开始理解逻辑，再尝试优化版本；中级开发者则可通过比较不同算法的效率，深入掌握数学优化技巧。

素数判断不仅是一个算法问题，更体现了数学与编程的结合。掌握这一问题的解决方法，不仅能提升编程能力，还能为后续学习更复杂的算法（如RSA加密）打下基础。建议读者动手实践代码，尝试输入不同的数值，观察输出结果，从而加深理解。