判断一个大于 2 的正整数 n 是否为素数,请用至少两种方法实现。c++
时间: 2024-05-05 12:21:53 浏览: 13
方法一:试除法
首先,素数的定义是只能被 1 和自身整除的数,因此我们可以从 2 开始往上试除,如果能被整除,则不是素数,否则是素数。
代码实现:
```c++
bool isPrime(int n) {
if (n <= 2) { // 小于等于 2 不是素数
return false;
}
for (int i = 2; i <= sqrt(n); i++) { // 从 2 到 sqrt(n) 试除
if (n % i == 0) { // 能被整除,不是素数
return false;
}
}
return true; // 不能被整除,是素数
}
```
方法二:埃氏筛法
埃氏筛法是一种筛选素数的方法,从 2 开始,将能被 2 整除的数都筛选掉,然后再从 3 开始,将能被 3 整除的数都筛选掉,以此类推,直到筛选到 sqrt(n) 为止,剩下的数就是素数。
代码实现:
```c++
bool isPrime(int n) {
if (n <= 2) { // 小于等于 2 不是素数
return false;
}
vector<bool> is_prime(n + 1, true); // 初始化所有数为素数
for (int i = 2; i <= sqrt(n); i++) { // 从 2 到 sqrt(n) 筛选
if (is_prime[i]) { // i 是素数
for (int j = i * i; j <= n; j += i) { // 将 i 的倍数筛选掉
is_prime[j] = false;
}
}
}
return is_prime[n]; // n 是否是素数
}
```