c++ 素数判断代码 c++判断质数最高效算法

该函数通过试除法优化判断质数：先处理小于等于3的数，排除能被2或3整除的数，再从5开始循环检查形如6k±1的数是否为因子，若存在则非质数，否则为质数。

判断一个数是否为质数（素数）是编程中的常见问题。在 C++ 中，实现高效质数判断的关键在于减少不必要的计算。以下是一个高效且实用的素数判断函数，适用于大多数场景，包括大数判断。

基础原理：试除法优化

一个合数必定有一个小于等于其平方根的因子。因此只需检查从 2 到 √n 的整数即可。

进一步优化：

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

• 先处理 2 和 3 的特殊情况
• 之后只检查形如 6k±1 的数（因为所有大于 3 的质数都满足这个形式）
• 跳过偶数和能被 3 整除的数

C++ 高效质数判断代码

以下是经过优化的判断函数：

#include <iostream>
#include <cmath>
<p>bool isPrime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;</p><pre class="brush:php;toolbar:false;">// 检查形如 6k ± 1 的因子
for (int i = 5; i * i <= n; i += 6) {
    if (n % i == 0 || n % (i + 2) == 0)
        return false;
}
return true;

登录后复制

}

标签： ai c++ ios stream 常见问题 质数