前言：
判断素数是编程中经常应用的实例，是编程学习的重要知识，那么下面我将介绍五种判断素数的方法。
定义：
素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
简单来说就是，如果一个数只能被1和它本身整除，那么这个数就是素数。
比如：2 3 5 7 11 23…
0和1既不是素数也不是合数，2是最小的素数。
方法（一）暴力法
最简单最暴力的方法就是根据定义，判断n是不是素数，则把1~n
内所有数都遍历，若都不能整除则为素数。因为如果n为素数，则只有1和n为因数。
代码如下：
方法（二）优化
上述方法效率极低，如果n为一万，则核心代码要跑n-2次，其实我们只需要判断2~√n个数，因为一个数如果可以因数分解（不是质数），那么分解得到的两个数一定是一个小于等于√n，一个大于等于√n，一个合数一定由两个自然数相乘，一个大于等于平方根一个小于等于平方根，并且成对存在，所以只判断前根号个。这时我们需要使用sqrt函数来求根号。
代码如下：
方法（三）孪生素数法
结论1：
当n>=5时，不在6x（x≥1）两侧的肯定不是素数，但在6x（x>=1）两侧的并不是一定就是素数。意思6x-1和6x+1可能为素数。
证明：
当n>=5时，若n为素数，n一定出现在6x（x>=1）的两侧。
6x-2 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1)…
观察得： 6x-2 = 3(x-1)，6x = 2(3x)，6x+2 = 2(x+1) …显然他们都不是素数
所以当n>=5时，素数一定在6x两边。
但是当x = 9时，6(x+1) = 55，可以被5整除，所以6x两侧不一定是素数。
结论2：
若n≥6且n-1和n+1为孪生素数，那么n一定是6的倍数。
证明：
因为孪生素数是差值为2的相邻素数。所以n-1和n+1是素数(小结论1)
所以 n-1和n+1一定是奇数，则n是偶数，所以n是2的倍数 (小结论2)
我们再假设n不是3的倍数，则n = 3x+1 或 n = 3x+2，
如果n = 3x+1，则n-1=3x，n-1可能为偶数，与小结论1违背
如果n = 3x+2，则n+1=3(x+1)，n+1可能是偶数，与小结论2违背
所以n不是3的倍数不成立，
所以n是3的倍数，又结合小结论2：
n是一定是6的倍数，所以代码增量为6，再判断n+1和n-1是否可以
于是乎代码如下：
方法（四）埃筛法
埃筛很简单，因为素数只能被1或者它本身整除，所以一个数的倍数一定不是素数，下面举个栗子：
2 为素数，则4 6 8 10 12 14 16等都不是素数
如此简但，直接上代码：
#include<stdio.h>#include<stdlib.h>#include<string.h>int main(){ int n,i,j; scanf("%d",&n); int vis[100000]={1,1};//0和1不是素数其他先默认为0 for(i=2;i<100000;i++){ if(vis[i]==0){ for(j=i+i;j<10000;j+=i){ vis[j]++; } } } if(vis[n]==0)printf("%d是素数",n); else printf("%d不是素数",n); return 0;}方法（五）欧式筛法
欧式筛法是埃筛的改进，相信大家一定注意到了埃筛的小问题
当i = 2时 我们遍历了4 6 8 10 12
当i = 3时 我们遍历了6 9 12 15
我们发现了6和12被重复筛出，这样的例子数不胜数，大大降低了效率
现在我们伟大的欧拉函数来了，数学的魅力就这里绽放
1：任何一个合数都可以分解成一个素数×一个数
2：i = m * n，m是最小质因子(素数=质数)
若n为合数，n= x*y，x是一个质数，且x>m
则i = mn = mxy = xmy，且my = k.
则i = x*k，且 x>m
说明一个合数与一个质数的乘积，可以表示为一个更大的合数和一个更小的质数的乘积。
代码如下：
输入一个n，打印出以内所有素数。