寒假训练 ACM笔记心得--欧拉筛法

欧拉筛法的一些笔记

看了一些大牛的心得，总结了一下自己的心得

代码所示：

#include<iostream>
using namespace std;
#define maxn ;
int main()
{
int sum=1;
int prime[maxn];
int vis[maxn];
 for(int i=2;i<maxn;i++)
{
if(!vis[i])
prime(sum++)=i;//找素数，把当前最小素数从筛子中，打入表里
    	   for(j=1;j<sum&&i*prime[j]<maxn;j++)//从表中选取这些数，依次翻倍
    	{
		vis[i*prime[j]]=1;//将这个数的i倍从筛子中删去
		if(i%prime[j]==0)//**关键的一步 放在后面讲**
		break;
		}

}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

关键一步：因为这个表是按照递增顺序的，所以当i%prime[j]==0的时候，说明i的最小质因子已经出现了。设i=nprime[j]；
又因为 是递增的 prime[j+1]>prime[i]
所以 iprime[j+1]=n*prime[j]*prime[j+1]
不是按照最小的质因子去筛，这样将会重复筛去，不能达到o（n）的时效。