C++判断一个数是质数的函数
时间: 2023-09-11 18:11:47 浏览: 95
以下是一个用C++编写的判断一个数是质数的函数:
```c++
bool isPrime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i <= sqrt(n); ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
```
在这个函数中,我们首先判断输入的数是否小于等于1,如果是,那么它不是质数,直接返回false。如果不是,我们从2开始,一直循环到该数的平方根,判断是否能被其中的一个数整除,如果能,那么它不是质数,直接返回false。如果循环结束,仍未找到可以整除的数,那么它是质数,返回true。
相关问题
c++判断一个数是质数
在 C++ 中,可以使用以下代码来判断一个数是否为质数:
```cpp
#include <iostream>
bool isPrime(int num) {
if (num <= 1) {
return false;
}
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
int main() {
int num;
std::cout << "请输入一个整数: ";
std::cin >> num;
if (isPrime(num)) {
std::cout << num << " 是质数" << std::endl;
} else {
std::cout << num << " 不是质数" << std::endl;
}
return 0;
}
```
上述代码定义了一个名为 `isPrime` 的函数,用于判断一个整数是否为质数。在 `main` 函数中,我们首先获取用户输入的整数,然后调用 `isPrime` 函数来进行判断,并输出相应的结果。
该方法使用了试除法来判断质数。它从2开始,依次将待判断的数与2到sqrt(num)之间的每个数进行取模运算,如果存在一个能整除的数,则说明该数不是质数。否则,该数就是质数。
希望这个示例能帮助到你!
C++判断一个数是质数的函数,时间最优!
以下是一个时间复杂度最优的C++函数,用于判断一个数是否为质数。
```c++
bool isPrime(int n) {
if (n <= 1) {
return false;
}
else if (n <= 3) {
return true;
}
else if (n % 2 == 0 || n % 3 == 0) {
return false;
}
int i = 5;
while (i * i <= n) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
i += 6;
}
return true;
}
```
在这个函数中,我们首先判断输入的数是否小于等于1,如果是,那么它不是质数,直接返回false。然后,我们判断输入的数是否小于等于3,如果是,那么它是质数,直接返回true。接着,我们判断输入的数是否能被2或3整除,如果能,那么它不是质数,直接返回false。
最后,我们用6k ± 1的形式进行循环,这是因为质数要么是6k + 1,要么是6k - 1。我们从5开始,每次加6,检查6k-1和6k+1是否能整除该数。如果存在一个数能够整除该数,那么它不是质数,直接返回false。如果循环结束,仍未找到可以整除的数,那么它是质数,返回true。
这个函数的时间复杂度是O(sqrt(n)/6),时间效率非常高。