质数筛

本文将介绍两周质数筛算法，分别是埃拉托斯特尼筛法（简称埃氏筛）与欧拉筛。

埃氏筛
基本思想:任意整数x的倍数2x，3x ···都不是质数，可以除去
算法基本流程:从2开始，从小到大扫描每个数字x，将它的倍数2x，3x ···，(lfloor N/x floor *x)如果没标记的就打上合数标记
，当扫描到x时，若x未被标记，则说明x不能被2~x-1的数整除，所以x是质数。
引用https://www.cnblogs.com/orion7/p/7491484.html的一张图片

另外，我们可以发现，有些数字会被重复标记，比如6会被2和3标记。浪费了时间。
实际上，小于(x^2)的x的倍数在扫描到x之前就已经被标记了。因此，我们可以加个小优化，让x的倍数从(x^2)开始枚举。（虽然是小优化，但是在洛谷却是100pts和40pts的差距)

inline void Eratosthenes1(int n) {
	for(int i = 2; i<= n; i++) {
		if(vis[i]) continue;
			prime[++cnt] = i ;
			for(int j = i;1ll* i * j <=1ll* n; j++)
				vis[i * j] = true;
	}
}

时间复杂度$$O（sum_{质数p le N} frac{N}{p} ) =O(N loglog N)$$
证明见https://zhuanlan.zhihu.com/p/272483362(太弱了，不会证明，以后一定补上):

欧拉筛（线性筛)
即使埃氏筛优化了，也还是会重复标记一些数字，比如12被2，3重复标记了，原因在于我们没有确定12的唯一产生方式。
根据算术基本定理，每个大于1的自然数都有唯一的有限个素数乘积表示,所以我们在生成一个需要被标记的合数时，只要在现有的数乘上一个质因子，并且让这个质因子是这个合数的最小质因子。采用该法，每个合数只会被它的最小质因数筛一次。

inline void EulerSieve(int n) {
	for(int i(2); i <= n; ++i) {
      if(!v[i])//v[i]记录i的最小质因子 
      {
      	v[i]=i;//如果i是质数，那么它只有两个因子，1和它本身，所以它的最小质因子为i 
      	prime[++cnt]=i;
	  }
      for(int j=1;j<=cnt;++j){
      	if(prime[j]>v[i]||prime[j]>n/i) break;
		  //i有比prime[j]更小的质因子或者i乘prime[j]会超出范围了 
		 v[prime[j]*i]=prime[j]; 
	  }
	}
}