判断素数的高效方法是检查2到√n间的因子。基础优化：n
判断一个数是否为素数（质数）是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的形式。利用这一点可以大幅减少判断次数。
立即学习“C++免费学习笔记（深入）”；
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是一种高效的概率性素数测试算法，适合大数场景。
基本思路是基于费马小定理和二次探测定理，通过多次随机测试来判断是否“极大概率”为素数。
#include using namespace std;long long modMul(long long a, long long b, long long mod) {return (__int128)a * b % mod;}
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;}
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;}
bool isPrime(long long n) {if (n < 2) return false;if (n == 2 || n == 3) return true;if (n % 2 == 0) return false;
// 对于 32 位整数，使用这些底数可保证正确性vector bases = {2, 7, 61};for (long long a : bases) { if (a >= n - 1) break; if (!millerRabin(n, a)) return false;}return true;
}
该实现对32位以内的整数完全准确。对于更大的数，可增加测试底数（如2, 325, 9375, 28178, 450775, 9780504, 1795265022）以提高准确性。
基本上就这些。小数用6k±1法足够快，大数考虑Miller-Rabin。关键在于根据数据范围选择合适的方法。
以上就是C++如何判断一个数是素数_C++质数判断的高效算法实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1488567.html
微信扫一扫 
支付宝扫一扫 
