欧拉筛选法

如有不当，欢迎指正！ 2.欧拉筛选法（线性筛选法）     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 int flag**[10000];** //flag标记非素数 非素数记为0 memset**(flag,-1,sizeof(flag));** flag**[1]=0;**

int prime**[10000];** //prime用来存放素数 类似数列 int cnt**=0;** //当前prime有几个数据

int i**,j; **//循环控制变量

int n**;** scanf**("%d",&n);**//输入n 研究到n的素数

for**(i=2;i<=n;i++)** //外循环 从2到n { if**(flag[i])**        prime**[++cnt]=i; **//如果这个数没有在前几轮标记中被标记为素数 就认为它不是素数

for**(j=1;j<=cnt&&iprime[j]<=n;j++) //内循环 从第一个素数开始 {                 flag[iprime[j]]=0;** //把外循环数字和到此为止每个素数的乘积标记为非素数 if**(i%prime[j]==0)** break**;** //如果外循环数字是这个素数的若干倍 结束内循环 }

}

for**(i=1;i<=cnt;i++)** //输出 printf**("%d ",prime[i]);**

这个算法高明之处在于 每个要被筛去的数（即合数） 都只在自己最小质因数的内循环中被筛去

约定：p表示最小质因数 b表示倍数（外循环数） a表示某个要被筛去的数 几个疑难点： 1.为什么恒有b>=p 因为只有研究到b的时候，才能把b纳入prime

2.为什么a只能被最小质因数筛去

假如在某轮外循环中 a1=p1b a2=p2b a3=p3*b  检测到b%p3==0(或者说b/p3==n，n为整数) 中止 中止条件也可以理解为找到了b的最小质因数 因为是从最小质数往上找

a4=p4*b 假如不中止 将要进行的下一步

因为b%p3==n 所以a4=p4p3n p3才是b的最小质因数 当b'(指之后某一轮新的倍数)有b'=p4n时会筛去 而这个b'=p4n=p4*b/p3 >b（因为p4>p3）

3.怎么保证外循环的数在14行判断的时候 只要没有被前面的筛去就认为是素数 假如检测到a 而a是非素数(合数)， 那么一定能表示为n3=p*b 而p<n3 在前面已经被找出（见1） b<n3 但是怎么保证b不会因为中止条件而退出？ 要让b不会因为中止条件退出 只要保证b的最小质因数大于或等于p 因为p是n3的最小质因数 所以b的最小质因数一定大于p （假设p存在一个不等于p的最小质因数p' 那么p'也是n3的最小质因数 与p是n3的最小质因数矛盾） 这也保证了 检测到a为止 a及之前的所有质数和合数都被找出

这个算法的时间复杂度为O(n) 因为有几个数 就检测几遍 空间复杂度也为O(n) 故又称为线性筛