c++怎么判断一个数是不是质数_质数判断算法实现-C++-PHP中文网

c++怎么判断一个数是不是质数_质数判断算法实现

冰火之心

发布： 2025-10-05 10:48:01

原创

327人浏览过

判断一个数是否为质数的常用方法是试除法，只需检查从2到√n的因子。优化版利用6k±1法则，跳过被2或3整除的数，提升效率。代码实现包括基础版本和针对大数的改进版本，适用于不同场景。

c++怎么判断一个数是不是质数_质数判断算法实现

判断一个数是否为质数是C++编程中常见的基础问题。质数是指大于1且只能被1和自身整除的自然数，比如2、3、5、7、11等。下面介绍几种常用且高效的C++实现方法。

基本思路：试除法

最直观的方法是从2开始尝试用小于该数的所有数去除它，如果存在能整除的数，则不是质数。

但可以优化：只需要检查从2到sqrt(n)之间的数即可，因为如果n有一个大于√n的因子，那么必然有一个对应的小于√n的因子。

若 n < 2，不是质数
若 n == 2，是质数（唯一的偶数质数）
若 n 是偶数且大于2，不是质数
检查从3到√n的所有奇数是否能整除n

示例代码：

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

#include <iostream>
#include <cmath>
using namespace std;
<p>bool isPrime(int n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;</p><pre class='brush:php;toolbar:false;'>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;

登录后复制

}

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

除了2和3以外，所有质数都可以表示为6k±1的形式。我们可以利用这一点减少循环次数。

阿里云-虚拟数字人

阿里云-虚拟数字人是什么？ ...

查看详情

先排除能被2或3整除的数，然后从5开始，交替检查形如6k-1和6k+1的数。

改进版代码：

bool isPrimeOptimized(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
<pre class='brush:php;toolbar:false;'>for (int i = 5; i * i <= n; i += 6) {
    if (n % i == 0 || n % (i + 2) == 0)
        return false;
}
return true;

登录后复制

}

这种方法跳过了所有能被2或3整除的数，效率更高，适合判断较大的数。