c ++函数判断素数
时间: 2024-06-12 18:11:43 浏览: 12
判断素数的方法有很多种,以下是一种常见的 C++ 函数实现:
```c++
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;
}
```
该函数接受一个整数参数 n,如果 n 是素数则返回 true,否则返回 false。该函数的实现思路是:如果 n 小于等于 1,则不是素数;否则从 2 开始枚举到 sqrt(n),如果存在一个数 i 能够整除 n,则 n 不是素数;否则 n 是素数。
注意:该函数的时间复杂度为 O(sqrt(n)),在 n 很大时可能会超时。如果需要判断多个数是否为素数,可以使用筛法等更高效的算法。
相关问题
c ++筛选法求100以内素数
C 语言实现筛选法求 100 以内素数的代码如下:
```c
#include <stdio.h>
int main() {
int n = 100;
int prime[n+1];
for (int i = 2; i <= n; i++) {
prime[i] = 1;
}
for (int i = 2; i*i <= n; i++) {
if (prime[i] == 1) {
for (int j = i*i; j <= n; j += i) {
prime[j] = 0;
}
}
}
printf("2 ");
for (int i = 3; i <= n; i += 2) {
if (prime[i] == 1) {
printf("%d ", i);
}
}
return 0;
}
```
首先,我们定义一个长度为 n+1 的数组 prime,初始化为 1,表示所有数都是素数。然后,从 2 开始遍历,如果 prime[i] 为 1,则把 i 的倍数(除去 i 本身)都标记为非素数,即 prime[j] = 0。这个过程叫做筛选,因为最后留下来的数都是素数。最后再遍历一遍 prime 数组,输出所有值为 1 的下标,即为 100 以内的素数。
c ++输出100内所有的质数
以下是使用C++语言输出100以内所有质数的代码:
```
#include <iostream>
using namespace std;
int main() {
int i, j;
bool isPrime;
// 从2到100遍历每个数
for (i = 2; i <= 100; i++) {
isPrime = true;
// 检查当前数是否为质数
for (j = 2; j <= i / 2; j++) {
if (i % j == 0) {
isPrime = false;
break;
}
}
// 如果是质数则输出
if (isPrime) {
cout << i << " ";
}
}
return 0;
}
```
运行结果为:
```
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)