C++程序检查一个数是否为质数

在C++中，可以用各种方法来判断一个数是否为质数。这里我们将介绍两种常用的方法：暴力枚举和试除法。

暴力枚举

暴力枚举法是指从2开始到该数的平方根，逐个将该数除以2到其平方根之间的数，判断是否有余数，若有则该数为合数，否则为质数。具体实现代码如下：

bool isPrime(int n){
    if(n < 2) return false; // 2以下都是合数
    int s = sqrt(n);
    for(int i = 2; i <= s; i++){
        if(n % i == 0) return false; // 若有余数，返回false
    }
    return true; // 否则返回true
}

这里我们用sqrt()函数求出该数的平方根，避免了将该数除以所有小于它的数的麻烦。时间复杂度为 $O(\sqrt{n})$ 。

试除法

试除法是指从2到该数的平方根，逐个将该数除以2到其平方根之间的质数，判断是否有余数，若有则该数为合数，否则为质数。不同于暴力枚举，这里我们要将所有小于等于该数的质数先预处理出来。具体实现代码如下：

vector<int> primes; // 存储所有小于等于n的质数

void getPrimes(int n) { // 预处理小于等于n的质数
    primes.clear(); // 先清空
    bool *vis = new bool[n + 1]; // 标记数组
    memset(vis, false, sizeof(bool) * (n + 1)); // 初始化为false
    for(int i = 2; i <= n; i++){
        if(vis[i]) continue; // 如果该数已标记过，跳过
        primes.push_back(i); // 将该数存入质数数组
        for(int j = i + i; j <= n; j += i){
            vis[j] = true; // 标记该数的倍数为合数
        }
    }
    delete[] vis; // 释放内存
}

bool isPrime(int n) {
    if(n < 2) return false; // 2以下都是合数
    for(auto p : primes){
        if(p > sqrt(n)) break; // 只需试除到sqrt(n)
        if(n % p == 0) return false; // 若有余数，返回false
    }
    return true; // 否则返回true
}

这里我们先用getPrimes()函数预处理出小于等于该数的质数，并将它们存入vector数组primes中。这里利用了筛法求质数，时间复杂度为 $O(n \log\log n)$ 。然后，在isPrime()函数中，我们直接遍历primes数组，将每个质数除一遍，判断是否有余数。需要注意的是，当质数大于该数的平方根时，就不需要继续试除了（因为结果必定为整除）。

完整代码

#include <bits/stdc++.h>
using namespace std;

// 判断一个数是否为质数（暴力解法）
bool isPrime1(int n) {
    if (n < 2) return false;
    int s = sqrt(n);
    for (int i = 2; i <= s; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

// 判断一个数是否为质数（试除法）
vector<int> primes; // 存储所有小于等于n的质数

void getPrimes(int n) { // 预处理小于等于n的质数
   primes.clear();
    bool *vis = new bool[n + 1]; // 标记数组
    memset(vis, false, sizeof(bool) * (n + 1)); // 初始化为false
    for (int i = 2; i <= n; i++) {
        if (vis[i]) continue; // 如果该数已标记过，跳过
        primes.push_back(i); // 将该数存入质数数组
        for (int j = i + i; j <= n; j += i) {
            vis[j] = true; // 标记该数的倍数为合数
        }
    }
    delete[] vis; // 释放内存
}

bool isPrime2(int n) {
    if (n < 2) return false;
    for (auto p : primes) {
        if (p > sqrt(n)) break;
        if (n % p == 0) return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    // 判断是否为质数
    if (isPrime1(n)) {
        cout << n << "是质数" << endl;
    } else {
        cout << n << "不是质数" << endl;
    }
    if (isPrime2(n)) {
        cout << n << "是质数" << endl;
    } else {
        cout << n << "不是质数" << endl;
    }
    return 0;
}

结论

通过本文的介绍，我们了解了C++中判断一个数是否为质数的两种方法：暴力枚举和试除法。其中，暴力枚举法的时间复杂度为 $O(\sqrt{n})$ ，而试除法则需要预处理小于等于该数的所有质数，时间复杂度为 $O(n \log\log n)$ 。当然，如果只需要判断一个数是否为质数，可以直接选择暴力枚举法。