用筛选法可得到2~n(n<10000)之间的所有素数,方法是:首先从素数2开始,将所有2的倍数的数从数表中删去(把数表中相应位置的值置成0);接着从数表中找下一个非0数,并从数表中删去该数的所有倍数;依此类推,直到所找的下一个数等于n为止。这样会得到一个序列:2,3,5,7,11,13,17,19,23,…用C语言
时间: 2024-02-20 07:56:46 浏览: 26
实现筛选法求2~n之间的所有素数的代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
void sieve(int n) {
int *prime = (int *) malloc((n + 1) * sizeof(int)); // 分配内存空间
int i, j;
for (i = 2; i <= n; i++) { // 初始化数表
prime[i] = 1;
}
for (i = 2; i * i <= n; i++) { // 筛选法
if (prime[i]) {
for (j = i * i; j <= n; j += i) {
prime[j] = 0;
}
}
}
printf("2 "); // 输出2
for (i = 3; i <= n; i += 2) { // 输出所有素数
if (prime[i]) {
printf("%d ", i);
}
}
free(prime); // 释放内存空间
}
int main() {
int n;
printf("请输入一个正整数n:");
scanf("%d", &n);
printf("2~%d之间的所有素数为:\n", n);
sieve(n);
printf("\n");
return 0;
}
```
运行结果示例:
```
请输入一个正整数n:50
2~50之间的所有素数为:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)