素数筛(埃氏筛法、欧拉筛法)

• 普通判别素数

从2到n枚举根号n次

bool isprime(int n){
	for(int j=2;j*j<=n;j++){
		if(i%j==0) return 0;
	}
	return 1;
}

• 埃拉托斯特尼筛法

基本思想：要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

表中有2到n的所有整数，其中2是最小的素数。将2记为素数，然后把表中2的倍数全部去掉。接下来表中最小的数是3，3不能被更小的数整除，所以3是素数，将表中所有3的倍数去掉。
以此类推，如果表中剩余的最小数为m,那么m就是素数，然后将表中m的倍数全部去掉。这样反复枚举就能够得到n以内的所有素数。

时间复杂度：O(nloglogn)。

#include<bits/stdc++.h>
const int maxn=1e5;
bool vis[maxn];
int prime[maxn],x=0;
void Eprime(int n){//埃氏筛
	for(int i=2;i<=n;i++){
		if(!vis[i]) prime[x++]=i;
		for(int j=2;i*j<=n;j++){
			vis[i*j]=1;
		}
	}
}

• 欧拉筛法

基本思想 ：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。
时间复杂度：O(n)
任何合数都能表示为素数之积，所以每个合数一定有一个最小质因子，每个合数都被其最小质因子筛去过一次，所以是线性时间

void oprime(int n){//欧氏筛
	for(int i=2;i<=n;i++){
		if(!vis[i]) prime[x++]=i;
		for(j=0;j<x&&i*prime[j]<=n;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0) break;//找到i*prime[j+k]的最小质因子为prime[j]，跳出循环
		}
	}
}

• 关于if(i%prime[j]==0)

如果i%prime[j]==0,i是prime[j]的整数倍，那么记m=i/prime[j]
所以i=m*prime[j]
如果继续内层循环，j+1
设k=i*prime[j+1]
可以得到：
k=i*prime[j+1]=(m*prime[j])*prime[j+1]
=(m*prime[j+1])*prime[j]
这说明i*prime[j+1]是prime[j]的整数倍，即k是prime[j]的整数倍，prime[j]才是k的最小质因子，所以不需要再进行标记，跳出内层循环。
当之后外层循环枚举到i=m*prime[j+1]时，该数k=(m*prime[j+1])*prime[j]会在内层循环中被i*prime[j]标记。
对于prime[j+2]及之后的素数也是如此。
所以，为了避免重复标记，让循环在i%prime[j]==0时跳出

例如：

• 枚举2，2是素数，放入素数表，排除4
• 枚举3，3是素数，放入素数表，排除6，9
• 枚举4，4不是素数，执行下一步，排除8，4%2=0跳出内层循环，该内层循环原本下一个数是4*3=12
• 枚举5，5是素数，放入素数表，排除10，15，20
• 枚举6，6不是素数，排除12，18，这里12被6*2筛掉
• 枚举7，7是素数，放入素数表，排除14
• 枚举8，8不是素数，排除16，8%2=0跳出内层循环

其中，如果第三步不在4中跳出，那么12将会被重复标记