企业官网建设流程全解析

1. 什么是素数

素数（又称质数）是指大于 1的自然数中，除了 1 和它本身以外不再有其他因数的数。例如 2、3、5、7、11 都是素数，而 4、6、8、9 都不是素数。

判断一个数是否为素数，是 C 语言初学者最经典的练习题目之一，也是后续学习算法优化、数论的基础。

2. 最基础的判断方法

最直观的思路：对于一个数n，从 2 开始一直试除到n-1，如果中间存在某个数能整除n，则n不是素数；否则n是素数。

#include<stdio.h>intisPrime(intn){if(n<=1){return0;// 1 和负数不是素数}for(inti=2;i<n;i++){if(n%i==0){return0;// 能被整除，不是素数}}return1;// 是素数}intmain(){intnum;printf("请输入一个整数：");scanf("%d",&num);if(isPrime(num)){printf("%d 是素数\n",num);}else{printf("%d 不是素数\n",num);}return0;}

这种方法虽然正确，但效率较低。当n很大时，循环次数接近n次，时间复杂度为 O(n)。

3. 优化一：只需判断到 √n

观察可以发现：如果n有一个大于√n的因数a，那么必然存在一个小于√n的因数b = n / a。因此，我们只需要从 2 试除到√n即可。

#include<stdio.h>#include<math.h>intisPrime(intn){if(n<=1){return0;}for(inti=2;i<=sqrt(n);i++){if(n%i==0){return0;}}return1;}

这样时间复杂度降为 O(√n)，性能大幅提升。

4. 优化二：跳过偶数

除了 2 以外，所有偶数都不是素数。因此可以先单独判断 2，然后从 3 开始只检查奇数。

intisPrime(intn){if(n<=1){return0;}if(n==2){return1;// 2 是素数}if(n%2==0){return0;// 偶数不是素数}for(inti=3;i<=sqrt(n);i+=2){if(n%i==0){return0;}}return1;}

这样循环次数又减少了一半，效率进一步提升。

5. 综合示例：输出 1~100 之间的所有素数

下面把上面的优化综合起来，输出 1 到 100 之间的所有素数：

#include<stdio.h>#include<math.h>intisPrime(intn){if(n<=1){return0;}if(n==2){return1;}if(n%2==0){return0;}for(inti=3;i<=sqrt(n);i+=2){if(n%i==0){return0;}}return1;}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 97

6. 进阶：埃拉托斯特尼筛法

当需要一次性判断大量数字（比如求 1 到 1000000 之间所有素数）时，逐个判断效率太低。此时可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes），时间复杂度为 O(n log log n)。

基本思想：从 2 开始，把每个素数的倍数都标记为合数，剩下的就是素数。

#include<stdio.h>#include<stdbool.h>voidsieve(intn){bool isPrime[n+1];for(inti=0;i<=n;i++){isPrime[i]=true;}isPrime[0]=isPrime[1]=false;for(inti=2;i*i<=n;i++){if(isPrime[i]){for(intj=i*i;j<=n;j+=i){isPrime[j]=false;}}}printf("1~%d 之间的素数有：\n",n);for(inti=2;i<=n;i++){if(isPrime[i]){printf("%d ",i);}}printf("\n");}intmain(){sieve(100);return0;}

7. 总结

掌握素数的判断方法，不仅能帮助你通过 C 语言的基础练习，更是理解算法复杂度优化的重要一步。建议初学者先掌握基础写法，再逐步理解优化思路，最后尝试用筛法解决更大规模的问题。