素数 埃氏筛 欧拉筛(线性筛)

【素数筛】 埃氏筛 欧拉筛（线性筛）

​ 素数筛是一种用来筛选自然数n以内全部素数的算法。

埃氏筛 (Sieve of Eratosthenes)

​ 埃氏筛的原理很容易理解，任意一个合数都可以表示成一个自然数i和一个素数的乘积，因此，如上图，筛出素数的倍数，剩下的就是素数。

代码

//在primes中值为true的是合数 
bool primes[MAXN] = {1, 1, 0};

void eraSieve(int n){
	for(int i = 2; i * i < n; ++i)
		if(!primes[i])							//i为素数
			for(int j = i * i; j <= n; j += i)	//标记i的倍数为合数
				primes[j] = 1;
}

---

代码注意点：

1. 外层循环的终止条件是i * i < N，因为只需要把不大于根号n的所有素数的倍数剔除就可以了。
2. 内层循环，起始j = i * i，小于i * i的之前已经被去除了。

欧拉筛

​ 欧拉筛是一个线性筛法，在埃氏筛中有的合数有多组因子，比如36，这样的合数就会被多次标记，不妨规定每个合数只用最小的一个质因数去筛，这就是欧拉筛了。使用到的定理

​ ==n = Factorymax * P==

​ 上式中，==n==是一个合数，每一个合数可以唯一的表示成如上形式。

其中Factory是除了==n==以外的最大的==n==的因数。而P满足如下两点：

1. P是一个素数

2. P小于等于Factory的所有因数

证明详见阳离子博客

代码

int primes[MAXN];		//0~N内的素数集合 

void eulerSieve(int n){
	int sum = 0;		//已经找到的素数的数量 
	bool flag[MAXN] = {false};		//标记是否为合数  
	for(int i = 2; i <= n; ++i){
		if(!flag[i])
			primes[sum++] = i;
		for(int j = 0; i * primes[j] <= n; ++j){
			flag[i * primes[j]] = true;		//标记素数的倍数为合数 
			if(i % primes[j] == 0) break;	//primes[j]同时是i和i*primes[j]的最小质因数 
		}
	}
}