该函数通过试除法优化判断质数：先处理小于等于3的数，排除能被2或3整除的数，再从5开始循环检查形如6k±1的数是否为因子，若存在则非质数，否则为质数。
判断一个数是否为质数（素数）是编程中的常见问题。在 C++ 中，实现高效质数判断的关键在于减少不必要的计算。以下是一个高效且实用的素数判断函数，适用于大多数场景，包括大数判断。
基础原理：试除法优化
一个合数必定有一个小于等于其平方根的因子。因此只需检查从 2 到 √n 的整数即可。
进一步优化：
立即学习“C++免费学习笔记（深入）”；
先处理 2 和 3 的特殊情况之后只检查形如 6k±1 的数（因为所有大于 3 的质数都满足这个形式）跳过偶数和能被 3 整除的数
C++ 高效质数判断代码
以下是经过优化的判断函数：
#include #includebool isPrime(int n) {if (n <= 1) return false;if (n <= 3) return true;if (n % 2 == 0 || n % 3 == 0) return false;
// 检查形如 6k ± 1 的因子for (int i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return false;}return true;
}
// 示例使用int main() {int num;std::cout > num;
if (isPrime(num)) std::cout << num << " 是质数。n";else std::cout << num << " 不是质数。n";return 0;
}
算法效率分析
该算法时间复杂度为 O(√n)，但相比朴素试除法减少了约 2/3 的循环次数。原因如下：
排除了所有偶数（除 2）排除了所有能被 3 整除的数（除 3）只测试可能为质数的形式：6k−1 和 6k+1
对于一般用途（如竞赛、工程），这种写法已经非常高效。
特殊情况说明
若需频繁判断多个数是否为质数，建议使用埃拉托斯特尼筛法预处理出一定范围内的所有质数，查询可达到 O(1) 时间。
基本上就这些。这个版本在速度与代码简洁之间取得了良好平衡，适合实际使用。
以上就是c++++ 素数判断代码 c++判断质数最高效算法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1489402.html
微信扫一扫 
支付宝扫一扫 
