c++怎么判断一个数是不是素数_c++判断素数的常见算法-C++-PHP中文网

c++怎么判断一个数是不是素数_c++判断素数的常见算法

穿越時空

发布： 2025-10-21 17:23:01

原创

454人浏览过

答案是判断素数常用试除法，从2到√n依次试除，若存在整除则非素数，优化方法包括只检查奇数和使用埃氏筛法预处理。

c++怎么判断一个数是不是素数_c++判断素数的常见算法

判断一个数是否为素数是C++编程中的常见问题。素数是指大于1且只能被1和自身整除的自然数，比如2、3、5、7、11等。下面介绍几种常用的C++判断素数的方法，从基础到优化逐步讲解。

1. 基础方法：试除法

最直接的方法是尝试用2到n-1之间的所有数去除n，如果存在能整除的数，则n不是素数。

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i < n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

登录后复制

说明： 这种方法简单直观，但效率低，时间复杂度为O(n)，不适合大数判断。

2. 优化方法：只检查到√n

如果n有一个大于√n的因数，那么必然有一个小于√n的对应因数。因此只需检查从2到√n即可。

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

#include <cmath>
<p>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 <= sqrt(n); i += 2) {
if (n % i == 0)
return false;
}
return true;
}</p>

登录后复制

说明： 排除了偶数后只检查奇数，将循环次数减少一半，时间复杂度降到O(√n)，适用于大多数场景。

3. 进一步优化：预处理小素数 + 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;
<pre class='brush:php;toolbar:false;'>for (int i = 5; i * i <= n; i += 6) {
    if (n % i == 0 || n % (i + 2) == 0)
        return false;
}
return true;

登录后复制

}

说明： 利用了素数分布规律，进一步减少循环次数，效率更高，适合频繁判断大数的情况。

4. 多次查询时使用埃氏筛法预处理

如果需要判断多个数是否为素数，可以预先用埃拉托斯特尼筛法（Eratosthenes Sieve）生成素数表。

#include <vector>
void sieveOfEratosthenes(int maxN, vector<bool>& prime) {
    prime.assign(maxN + 1, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i * i <= maxN; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= maxN; j += i)
                prime[j] = false;
        }
    }
}
<p>// 使用示例
vector<bool> prime;
sieveOfEratosthenes(100000, prime);
if (prime[97]) cout << "97是素数";</p>

登录后复制

说明： 适合在已知范围内的多次查询，预处理O(n log log n)，单次查询O(1)。

基本上就这些常见的C++判断素数方法。根据实际需求选择：单次判断用优化试除法，大量查询用筛法。注意处理边界情况如n≤1、n=2等。不复杂但容易忽略细节。

以上就是c++++怎么判断一个数是不是素数_c++判断素数的常见算法的详细内容，更多请关注php中文网其它相关文章！