素数算法吐血总结
扯淡
相信很多童鞋在OJ都遇到过关于素数的问题，对于素数相关问题，一般都会给出答案，但是相信并不是所有人能给出最优解，包括本菜鸟，故吐血整理一波，以供学习回顾。
素数定义
既然都说素数、质数什么的，那么什么是素数呢？
质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。大于1的自然数若不是素数，则称之为合数。
问题
对于素数相关问题，一般会有三种问题。
- 判断某个数是否为素数。
- 打印出小于自然数
N的素数。 - 对于给定的自然数
N，从小到大依次打印出N个素数。
素数判断
试除法
如果要判断某个自然数X是否为素数，，这就是试除法
初级版
假设要判断自然数X 是否为素数，最简单的想法就是判断X 是否能够整除1 ~ X 之间的某个数。
中级版
如果自然数X 存在质因数，那么必定会小于等于X/2, 所以稍微动脑的人会将返回缩小到1 ~ X/2, 减小一半的工作量
高级版
对于一个自然数，如果存在可整除的数，即X = a * b, 那么因数中必定会有一个因数小于, 而另一个因数大于。 故很多更聪明的程序猿会将返回缩小到1 ~
上面的算法仅仅是判断某个数是否为质数，可是要得出素数的序列，仅仅通过遍历自然数然后进行素数判断可是最傻的办法，那么有什么简单高效的算法呢？
筛法
质数算法中的重头戏就是要说的本算法。
埃拉托斯特尼筛法
基本思想
素数的倍数一定不是素数。
做法
首先申请空间为N+1 的数组用来保存自然数1 ~ N 是否为质数，起初将所有自然数全部置为0, (0 表示质数，1 表示合数)，从第一个素数2 开始，将2 的倍数全部置为1， 然后找到下一个素数3 ，将3 的倍数全部置为1， 直到找到最后一个小于N 的质数。此处引用*的示例图。
代码实现
void make_prime()
{
memset(prime, 1, sizeof(prime));
prime[0] = false;
prime[1] = false;
int N = 31700;
for (int i = 2; i < N; i++)
if (prime[i])
{
primes[++cnt ] = i;
for (int k = i + i; k < N; k += i)
prime[k] = false;
}
return;
}时间复杂度为O(nloglogn), 空间复杂度为O(n)
虽然已经很高效，但是仍然存在缺点，对于能够整除不同素数的自然数，筛了多次。例如30, 在素数2 的时候，k = 2 * 15 筛过一次，素数为3 的时候， k = 3 * 10 又筛过一次。故出现了下面的改进算法。
欧拉筛法
const long N = 200000;
long prime[N] = {0}, num_prime = 0;
int isNotPrime[N] = {1, 1};
int main()
{
for (long i = 2 ; i < N ; i ++)
{
if (! isNotPrime[i])
prime[num_prime ++] = i;
//关键处1
for (long j = 0 ; j < num_prime && i * prime[j] < N ; j ++)
{
isNotPrime[i * prime[j]] = 1;
if ( !(i % prime[j] ) ) //关键处2
break;
}
}
return 0;
}理解
首先，先明确一个条件，任何合数都能表示成一系列素数的积。 不管 i 是否是素数，都会执行到“关键处1”。
如果 i 都是是素数的话，那简单，一个大的素数 i 乘以不大于 i 的素数，这样筛除的数跟之前的是不会重复的。筛出的数都是 N=p1*p2的形式, p1，p2之间不相等
如果 i 是合数，此时 i 可以表示成递增素数相乘 i=p1p2…*pn, pi都是素数（2<=i<=n）， pi<=pj ( i<=j ) p1是最小的系数。
根据“关键处2”的定义，当p1==prime[j] 的时候，筛除就终止了，也就是说，只能筛出不大于p1的质数*i。
我们可以直观地举个例子：i=2*3*5 此时能筛除 2*i ,不能筛除 3*i， 如果能筛除3*i 的话，当 i’ 等于 i’=3*3*5 时，筛除2*i’ 就和前面重复了。