欧拉筛（线性筛）_欧拉筛时间复杂度

欧拉筛多用于筛素数，时间复杂度是o(n);
主要原理：合数=最小质因子*合数（质数）
这个合数的组成是唯一的，欧拉筛里面只在这种情况筛一次，也就是每个数就筛一次，可以完成o(n)的复杂度。
每当枚举到一个数，把这个数当作后面的那个数，在已经得到的质数里枚举当作最小质因子，看看这样的组合能找到哪个合数，但是要注意，前面的质数一定要是最小质因子，如果if(i%prim[j]==0)则，前面的质数不是最小质因子，因为i可以拆成更小的质因子，导致prim[j]不是将要得到的合数的最小质因子，这样会造成这个将要得到的合数被筛两遍，徒增复杂度；

	//欧拉筛//
	 for(i=2;i<=n;i++)
	 {
	 	if(!vis[i])
	 	{
	 		prim[sum++]=i;
		 }
		 for(j=0;j<sum;j++)
		 {
		 	if(prim[j]*i<=n)
		 	vis[prim[j]*i]=true;
		 	else
		 	break;
		 	if(i%prim[j]==0)
		 	break;
		 }
	 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18