c语言求素数

### C语言实现求素数的程序 以下是用C语言编写求素数的几种方法，结合了多种优化思路和代码示例。 #### 方法一：基本判断法 通过从2到`num/2`逐一检查是否能整除给定数字`num`，如果存在任何整除情况，则该数字不是素数。 ```c #include <stdio.h> #include <stdbool.h> int main() { int i, num; _Bool flag = 1; printf("请输入一个整数："); scanf("%d", &num); for (i = 2; i < num / 2; i++) { if (num % i == 0) { flag = 0; break; } } if (flag) { printf("%d 是一个素数！\n", num); } else { printf("%d 不是一个素数！\n", num); } return 0; } ``` 这种方法虽然简单易懂，但效率较低，尤其是在处理较大范围的数字时[^1]。 --- #### 方法二：平方根优化法 利用数学性质，仅需检查从2到`sqrt(num)`之间的所有整数即可。如果在该范围内没有找到可以整除的因子，则该数字为素数。 ```c #include <stdio.h> #include <math.h> int main() { int count = 4; // 已知2、3、5、7是素数 int i, j, k; _Bool flag = 1; for (i = 9; i < 10000; i++) { k = (int)sqrt((double)i); for (j = 2; j <= k; j++) { if (i % j == 0) { flag = 0; break; } } if (flag) { count++; } else { flag = 1; } } printf("10000以内共有%d个素数！\n", count); return 0; } ``` 此方法显著减少了不必要的计算，从而提高了程序运行效率[^2]。 --- #### 方法三：埃拉托色尼筛法 埃拉托色尼筛法是一种高效的算法，用于生成一定范围内的所有素数。其核心思想是逐步标记合数，剩下的未被标记的数字即为素数。 ```c #include <stdio.h> #include <stdlib.h> #define MAX 10000 int main() { int *prime = (int *)malloc((MAX + 1) * sizeof(int)); int i, j, count = 0; for (i = 0; i <= MAX; i++) { prime[i] = 1; // 初始化为1，表示可能是素数 } prime[0] = prime[1] = 0; // 0和1不是素数 for (i = 2; i * i <= MAX; i++) { if (prime[i]) { for (j = i * i; j <= MAX; j += i) { prime[j] = 0; // 将i的倍数标记为非素数 } } } for (i = 2; i <= MAX; i++) { if (prime[i]) { count++; } } printf("10000以内共有%d个素数！\n", count); free(prime); return 0; } ``` 埃拉托色尼筛法适用于需要一次性生成大量素数的情况，性能优越[^3]。 --- ### 相关说明 上述三种方法各有优劣： - **基本判断法**适合小范围内的素数判断，但效率较低。 - **平方根优化法**通过减少循环次数提升了效率，适合中等规模的素数计算。 - **埃拉托色尼筛法**则适用于大规模素数生成场景，具有更高的性能。 ---