高速判断素数的C++代码
时间: 2024-09-20 16:02:58 浏览: 3
在C++中,判断素数是一个常见的算法练习。这里提供一种简单的基于埃拉托斯特尼筛法(Sieve of Eratosthenes)的高效做法。这个方法主要用于生成一定范围内的所有素数。
```cpp
#include <iostream>
#include <vector>
std::vector<bool> sieve(int n) {
std::vector<bool> isPrime(n+1, true); // 初始假设所有数字都是素数
isPrime[0] = isPrime[1] = false; // 0和1不是素数
for (int i = 2; i * i <= n; ++i) { // 只需检查到i的平方根
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false; // 如果找到因子,则标记为非素数
}
}
}
return isPrime;
}
bool isPrimeFast(int num) {
if (num <= 1) return false;
if (num == 2 || num == 3) return true;
if (num % 2 == 0 || num % 3 == 0) {
return num > 3; // 如果能被2或3整除,且大于3,那么它不是素数
}
int sqrtNum = static_cast<int>(std::sqrt(num));
for (int i = 5; i <= sqrtNum; i += 6) { // 跳过2和3的倍数
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}