//——整理《洛谷tg》

质数与合数
质数，也称素数或不可约数
即除1和它本身以外没有其它正因数的数
 
合数，好像没听说过其他名字
即除1和质数以外的正整数

合数a一定存在一个不超过根号下a的质因子
上面这条性质可以帮助我们在O(n)的时间复杂度内检验质数

相信大家都听说过O(nlnnlnn)的Eratosthenes筛法
反正它似乎跑的不慢，



#include<bits/stdc++.h>
  for (int i=1;i<maxn;i++)
     for (int j=i<<1;j<maxn;j+=i)
       a[j]=0;


 线性筛
 这里介绍了下线性筛
 
 线性筛及其复杂度的证明
   for (int i=2;i*i<=maxn;i++)
     if (a[i]==0)
	   for (int j=i<<1;j<=maxn;j+=i)
	     a[j]=1;

线性筛中，每个数只会被它最小的质因子筛去

void Euler_Sieve(){
	for (int i=2;i<maxn;i++)
	{
	
	  if (!vis[i]){
	  	pri[tot++]=i;
	  }
	 for(int j=0;j<tot&&pri[j]*i<maxn;j++)
	   {
	   	vis[pri[j]*i]=1;
	   	if (i%pri[j]==0)
		     break; 
		} 
	} 
}

线性筛中，每个数只会被它最小的质因子筛去
比如，设i=35=5*7
则通过i筛去的数是2*i，3*i和5*i，即
 2*5*7=70
 3*5*7=105
 5*5*7-175
 
可以看成往原数中添加不超过i的最小质因子的质数
每个数只被筛了一次，所以保证线性
显然每个被筛去的数都只会被其最小的质因子pri[j]筛去一次。
所以这个算法复杂度是线性的。