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

本文最后更新于:2020年6月10日 下午

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

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

埃氏筛 (Sieve of Eratosthenes)

Era

​ 埃氏筛的原理很容易理解,任意一个合数都可以表示成一个自然数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]的最小质因数 
		}
	}
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!