1. 什么是素数
素数（质数）是指大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的数。例如 2、3、5、7、11 都是素数，而 4、6、8、9 不是素数。
2. 最基础的素数判断方法
最直观的思路是：对于一个数 n，从 2 开始一直试除到 n-1，如果存在某个数能整除 n，则 n 不是素数；否则 n 是素数。
#include<stdio.h>#include<stdbool.h>// 判断 n 是否为素数boolisPrime(intn){if(n<=1){returnfalse;// 1 和负数不是素数}for(inti=2;i<n;i++){if(n%i==0){returnfalse;// 能被整除，不是素数}}returntrue;}intmain(){intnum;printf("请输入一个整数：");scanf("%d",&num);if(isPrime(num)){printf("%d 是素数\n",num);}else{printf("%d 不是素数\n",num);}return0;}3. 优化一：只需判断到 sqrt(n)
上面的方法虽然正确，但效率较低。观察可以发现：如果 n 有一个大于 sqrt(n) 的因数，那么必然存在一个小于 sqrt(n) 的因数与之对应。因此，只需要判断到 sqrt(n) 即可。
#include<stdio.h>#include<stdbool.h>#include<math.h>boolisPrime(intn){if(n<=1){returnfalse;}// 只需判断到 sqrt(n)for(inti=2;i<=sqrt(n);i++){if(n%i==0){returnfalse;}}returntrue;}4. 优化二：跳过偶数
除了 2 以外，所有偶数都不是素数。因此可以先单独判断 2，然后从 3 开始只检查奇数，步长设为 2，这样可以将判断次数再减少一半。
#include<stdio.h>#include<stdbool.h>#include<math.h>boolisPrime(intn){if(n<=1){returnfalse;}if(n==2){returntrue;// 2 是唯一的偶素数}if(n%2==0){returnfalse;// 其他偶数都不是素数}// 只检查奇数for(inti=3;i<=sqrt(n);i+=2){if(n%i==0){returnfalse;}}returntrue;}5. 综合示例：输出 1~100 之间的所有素数
下面是一个完整的示例程序，输出 1 到 100 之间的所有素数：
#include<stdio.h>#include<stdbool.h>#include<math.h>boolisPrime(intn){if(n<=1){returnfalse;}if(n==2){returntrue;}if(n%2==0){returnfalse;}for(inti=3;i<=sqrt(n);i+=2){if(n%i==0){returnfalse;}}returntrue;}intmain(){printf("1~100 之间的素数有：\n");for(inti=1;i<=100;i++){if(isPrime(i)){printf("%d ",i);}}printf("\n");return0;}运行结果：
1~100 之间的素数有： 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 976. 总结
- 素数判断的核心思路是试除法：从 2 开始逐个尝试能否整除 n。
- 优化点一：判断范围缩小到 sqrt(n)，大幅减少循环次数。
- 优化点二：跳过偶数，只检查奇数，进一步减半。
- 对于更大范围的素数筛选（如求 1~N 内所有素数），还可以使用埃拉托斯特尼筛法（埃氏筛），效率更高，感兴趣的读者可以进一步学习。
