素数的求解

大一刚开始学习程序设计的时候，自己就遇到过素数求解的问题，今天又遇到在这里总结一下。
素数又称质数，为大于1的自然数中，除了1和整数自身外，没法被其他自然数整除的数。
因为素数没有特定的规律，最简单的方法就是使用穷举法了，我们判断一个数字是否为素数，就一个个的判断他是否能被其他的数整除，如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

#include <stdio.h>   /* 判断一个正整数是否素数 */ static int prime_number(const int n) { int i;   if (n == 2) return 0;   for (i = 2; i < n; i++) { if (n % i == 0) { return -1; } }   return 0; }   int main(void) { int i;   for (i =2; i < 100; i++) { if (prime_number(i) == 0) { printf("%3d ", i); } }   return 0; }

这里我们稍微深入思考一下，我就就很容易想到如下的信息：
1 偶数是不可能是素数的
2 判断奇数是否为素数是不需要那偶数去除它的
3 素数循环不必循环到n，到根号n就可（理论上为什么不清楚）
按以上的方法修改下程序，效率会提高很多，程序如下。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include <stdio.h>   /* 判断一个正整数是否素数 */ static int prime_number(const int n) { int i;   if (n == 2) return 0;   for (i = 3; i*i < n; i += 2) { if (n % i == 0) { return -1; } }   return 0; }   int main(void) { int i;   printf("%3d ", 2); for (i = 3; i < 100; i += 2) { if (prime_number(i) == 0) { printf("%3d ", i); } }   return 0; }