C++如何判断一个数是不是素数

当然，作为一个网站的作者，我很乐意为你提供详细的攻略。

在C++中判断一个数是否是素数，通常有两种方法：暴力枚举和筛法。

暴力枚举

暴力枚举是一种较为简单的方法，即对于一个数n，将n分别除以2,3,4,...,n-1，判断它是否能除尽这些数。若一旦出现n%i==0，则说明n不是素数。

暴力枚举的代码实现如下：

bool isPrime(int n) {
    if (n <= 1) return false;  // 排除小于等于1的数
    for (int i = 2; i <= n - 1; i++) {
        if (n % i == 0) return false;  // 如果 i 能够整除 n，则 n 不是素数
    }
    return true;
}

筛法

筛法则是一种更为高效的方法。常用的有埃氏筛法和线性筛法。

埃氏筛法

埃氏筛法的思路是，从2开始，将每个质数的倍数都标记成合数，以达到筛选素数的目的。其具体实现流程如下：

1. 初始化一个bool类型的数组isPrime，长度为n+1，表示每个数的状态，初始值都为true
2. 从2开始到$\sqrt{n}$，枚举所有质数p
3. 对于当前质数p，枚举它的倍数i，从2开始，将isPrime[ip]标记为false，即ip不是素数
4. 注意，为了避免重复标记，i从p开始枚举

埃氏筛法的实现如下：

vector<bool> isPrime(n+1, true);  // 初始化状态

for (int i = 2; i <= sqrt(n); i++) {
    if (isPrime[i]) {
        // 将质数的倍数标记成false
        for (int j = i*i; j <= n; j += i) {
            isPrime[j] = false;
        }
    }
}

// 统计素数的数量
int cnt = 0;
for (int i = 2; i <= n; i++) {
    if (isPrime[i]) cnt++;
}

return cnt;

线性筛法

线性筛法是埃氏筛法的升级版，它使用一个数组prime存储所有素数，并使用一个bool类型的数组isPrime表示每个数的状态，初始值都为true。具体实现流程如下：

1. 初始化一个空的数组prime，表示所有质数； 初始化一个bool类型的数组isPrime，长度为n+1，表示每个数的状态，初始值都为true
2. 从2开始到n，枚举所有数i
3. 如果i是质数，将它添加到数组prime中；同时，将i的倍数标记为合数，并设置isPrime[i*p]=false
4. 如果i不是质数，枚举prime数组中所有不超过i/p的素数p，如果i%p==0，则说明i不是素数，退出循环

线性筛法的实现如下：

vector<int> prime;  // 存储素数
vector<bool> isPrime(n+1, true);  // 初始化状态

for (int i = 2; i <= n; i++) {
    if (isPrime[i]) {
        prime.push_back(i);
    }
    for (int j = 0; j < prime.size() && i*prime[j] <= n; j++) {
        isPrime[i*prime[j]] = false;
        if (i % prime[j] == 0) {
            break;
        }
    }
}

// 统计素数的数量
int cnt = 0;
for (int i = 2; i <= n; i++) {
    if (isPrime[i]) cnt++;
}

return cnt;

至此，我们已经讲解了C++如何判断一个数是不是素数的完整攻略。其中，我们分别介绍了暴力枚举、埃氏筛法和线性筛法三种方法，其中埃氏筛法和线性筛法比暴力枚举更加高效，可以在处理大量数据时发挥更大的优势。