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

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

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

2025-12-12

浏览次数：次

返回列表

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

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

判断一个数是否为素数（质数）是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的形式。利用这一点可以大幅减少判断次数。

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。在实际测试中比前一种更快。

处理大数：Miller-Rabin 概率算法

当n非常大（如超过1e18）时，确定性算法太慢。Miller-Rabin是一种高效的概率性素数测试算法，适合大数场景。

Procys

AI驱动的发票数据处理

102 查看详情 Procys

基本思路是基于费马小定理和二次探测定理，通过多次随机测试来判断是否“极大概率”为素数。

#include <bits/stdc++.h>
using namespace std;
<p>long long modMul(long long a, long long b, long long mod) {
return (__int128)a * b % mod;
}</p><p>long long modPow(long long base, long long exp, long long mod) {
long long result = 1;
while (exp > 0) {
if (exp & 1) result = modMul(result, base, mod);
base = modMul(base, base, mod);
exp >>= 1;
}
return result;
}</p><p>bool millerRabin(long long n, long long a) {
if (n % a == 0) return false;
long long d = n - 1;
while (d % 2 == 0) {
if (modPow(a, d, n) == n - 1) return true;
d >>= 1;
}
long long temp = modPow(a, d, n);
return temp == 1 || temp == n - 1;
}</p><p>bool isPrime(long long n) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0) return false;</p><pre class='brush:php;toolbar:false;'>// 对于 32 位整数，使用这些底数可保证正确性
vector<long long> bases = {2, 7, 61};
for (long long a : bases) {
    if (a >= n - 1) break;
    if (!millerRabin(n, a)) return false;
}
return true;