前言
今天做ACM的时候，遇到了素数的检测，检测一个范围内的素数的时候，如果用最简单的那种方法，超时严重，因此学习了一个新的素数检测算法——素数筛选法，这里也是跟大家分享一下
素数
素数的定义
一个大于1的整数，如果不能被除1和它本身之外的其它正整数整除，则是素数（又称质数）
合数的定义
一个大于1的整数，如果不是素数则是合数。其中能整除这个数的正整数叫做约数，不等于1也不等于合数本身的约数叫做非平凡约数。
注意：
1既不是素数也不是合数
检测素数
所谓素数检测，就是给定任意一个大于1的整数，判断这个整数是否为素数。
因子检测法
方法：就是从2到ｎ-1一个个的拿来尝试，看能否整除ｎ，如果存在能够整数ｎ的（找到一个因子），则ｎ不是素数，否则认为ｎ是素数。实际，是不需要试探到ｎ-1的，只要的ｎ的二次方根即可，原因是：
设n = a * b,且a、b均为n非平凡约数，显然a > n的二次方根和b > n的二次方根不可能同时成立，因为同时成立时 a * b就会大于n，所以如果n存在非平凡约数，至少有一个小于等于n的二次方根，因此只要遍历到ｎ的二次方根即可。
因子检测的实现代码如下（ｃ）：
int isPrime(int n)
{
int i, flag;
flag = (n <= 1)? 0 : 1;
for(i = 2; i <= sqrt(n); i ++)
{
if(n % i == 0)
{
flag = 0;
break;
}
}
return flag;
}
测试结果：
时间复杂度：
很明显，因子检测算法的时间复杂度是0（ｎ的二次方根）,一般来说，这个时间复杂度已经很牛叉了，但是如果我要求ｎ以内所有的素数集合，那时间复杂度瞬间就到了n * n的二次方根，这个对于ｎ很大时是不可忍受的
素数筛选法
利用素数因子检测法去超找ｎ以内的所有素数，时间复杂度太高，不可忍受，因此这里介绍另外一种算法，素数筛选法，可以大大的节省时间，带来的直接功效是九度ａｃｍ关于素数检测的题我瞬间ａｃ，用素数因子检测基本都是ｗａ。
原理：
当i是素数的时候，则ｉ的所有倍数必然是合数。如果ｉ已经判断不是素数了，那么找到ｉ后面的质数来把这个质树的倍数筛掉。
求20以内素数的筛选过程：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
第一步，因为所有的偶数和0,1必然不是质数，则将这些数的对应的value标记为flase，其余为true。
第二步：
i = 3,由于prime[3] = 1,则prime[6],prime[9],prime[12],prime[15],prime[18]均标记为0;
i = 4,由于prime[4] = 0,则continue，不做处理;
i = 5 > sqrt(20),算法结束
时间复杂度：
这个时间复杂度由于我的数学知识有限，也没法把计算过程解释出来，总之确实是很快，至于为什么ｉ= 5就结束了，原因跟素数因子法里面的原理是一样的，因为ｎ的因子必然有一个是小于等于n的二次方根的。
素数筛选法实现代码：
void getPrimeArray(int *prime)
{
int i, j;
//初始化素数标识数组
for(i = 0; i < max; i ++)
{
if((i == 2 || i % 2 != 0) && i != 1)
{
prime[i] = 1;
} else
{
prime[i] = 0;
}
}
//进行素数的筛选
for(i = 2; i * i < max; i ++)
{
if(prime[i])
{
for(j = 2 * i; j < max; j += i)
{
prime[j] = 0;
}
}
}
}
参考资料
