基础试除法：判断2到n-1是否能整除n；2. 优化试除法：只需检查2到√n；3. 跳过偶数：大于2的偶数非素数；4. 埃拉托斯特尼筛法：批量求素数高效。
判断一个数是否为素数（质数）是C++编程中常见的问题。素数是指大于1且只能被1和自身整除的自然数。下面介绍几种常用的算法，从简单到高效，适用于不同场景。
1. 基础试除法
最直观的方法是尝试用2到n-1之间的所有数去除n，如果存在能整除的数，则n不是素数。
bool isPrime(int n) {
if (n if (n == 2) return true;
for (int i = 2; i if (n % i == 0)
return false;
}
return true;
}
这种方法逻辑清晰，但效率低，时间复杂度为O(n)，不适合大数判断。
2. 优化试除法：只检查到√n
如果n有一个大于√n的因数，那么必然有一个小于√n的对应因数。因此只需检查2到√n即可。
立即学习“C++免费学习笔记（深入）”；
bool isPrime(int n) {
if (n if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i = 3; i * i if (n % i == 0)
return false;
}
return true;
}
跳过偶数并只检查到√n，时间复杂度降为O(√n)，适合大多数实际应用。
3. 使用6k±1优化
除了2和3，所有素数都可以表示为6k±1的形式。可以利用这一点减少循环次数。
bool isPrime(int n) {
if (n if (n == 2 || n == 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
该方法进一步减少了需要检查的数，性能比前一种更好，尤其在处理大数时优势明显。
4. 筛法预处理：埃拉托斯特尼筛法
如果需要判断多个数是否为素数，可以预先生成素数表。使用埃氏筛一次性标记出范围内的所有合数。
#include
std::vector sieve(int n) {
std::vector isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i if (isPrime[i]) {
for (int j = i * i; j isPrime[j] = false;
}
}
return isPrime;
}
适用于需要频繁查询素数的场景，预处理时间复杂度为O(n log log n)，查询为O(1)。
基本上就这些常用方法。小数据用优化试除法，大数据或多次查询考虑筛法。理解每种算法的适用场景，能写出更高效的代码。
以上就是c++++如何判断一个数是否为素数_C++判断质数的几种算法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1482898.html
微信扫一扫 
支付宝扫一扫 
