C++判断是否为质数
时间: 2024-09-20 13:10:02 浏览: 32
在C++中,判断一个数是否为质数通常通过试除法(也称为暴力法)实现。质数是指只有1和它本身两个正因数的自然数。以下是简单的步骤:
```cpp
bool isPrime(int num) {
if (num <= 1) { // 小于等于1的数不是质数
return false;
} else if (num == 2 || num == 3) { // 2和3是特例,它们都是质数
return true;
} else if (num % 2 == 0 || num % 3 == 0) { // 质数不可能是2的倍数,除了2,也不可能同时是3的倍数
return false;
}
for (int i = 5; i * i <= num; i += 6) { // 只需要检查到num的平方根即可,因为大于这个数的因子必定成对存在
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true; // 如果能全部通过以上条件,则num是质数
}
```
相关问题
c++判断71是否为素数
可以使用以下代码来判断71是否为素数:
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n = 71;
if (n <= 1) {
cout << "not a prime number" << endl;
} else {
int i;
for (i = 2; i <= sqrt(n); i++) {
if (0 == n % i) {
break;
}
}
if (i > sqrt(n)) {
cout << "a prime number" << endl;
} else {
cout << "not a prime number" << endl;
}
}
return 0;
}
根据引用中的方法一,也可以使用以下代码来判断71是否为素数:
#include <bits/stdc++.h>
using namespace std;
bool is_su_shu(int n) {
if (n == 1) {
return false;
}
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
int main() {
int n = 71;
if (is_su_shu(n)) {
cout << "a prime number" << endl;
} else {
cout << "not a prime number" << endl;
}
return 0;
}
c++判断一个是否为素数
以下是一个 C++ 程序,用于判断一个数是否为素数:
```c++
#include <iostream>
using namespace std;
bool isPrime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
int main() {
int n;
cout << "请输入一个整数:";
cin >> n;
if (isPrime(n)) {
cout << n << " 是素数" << endl;
} else {
cout << n << " 不是素数" << endl;
}
return 0;
}
```
程序中的 `isPrime()` 函数用于判断一个数是否为素数,如果是素数则返回 `true`,否则返回 `false`。函数中的算法是:从 2 到 sqrt(n) 遍历所有可能的因子,如果找到一个能够整除 n 的因子,那么 n 就不是素数。如果遍历了所有可能的因子都没有找到能够整除 n 的因子,那么 n 就是素数。
在主函数中,先输入一个整数 n,然后调用 `isPrime()` 函数判断 n 是否为素数,并输出结果。