筛法求素数

筛法求素数

Eratosthenes 筛法

时间复杂度 \(O(n loglogn)\)。

关键优化：\(j\) 从 \(i \times i\) 开始

void getprime(int mx){
	memset(is_prime, 1, sizeof(is_prime));
	is_prime[0] = is_prime[1] = 0;
	F(i, 2, mx){
		if(is_prime[i]){
			prime[++cnt] = i;//存
			if(1ll * i * i > mx) continue;//判越界
			for(int j = i * i; j <= mx; j+=i) is_prime[j] = 0;//筛
			//因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i 
			//的倍数开始，提高了运行速度		
		}  
	}
}

Euler 筛法

时间复杂度 \(O(n)\)。

关键优化 \(i \mod prime[j]=0\) 就 \(break\)。

void getprime(int mx){
	memset(is_prime, 1, sizeof(is_prime));
	is_prime[0] = is_prime[1] = 0;
	F(i, 2, mx){
		if(is_prime[i]){
			prime[++cnt] = i;//存		
		}
		F(j, 1, cnt){
			if(1ll * prime[j] * i > mx) break;
			is_prime[prime[j] * i] = 0;
			if(!(i % prime[j])) break;
	        // i % pri_j == 0
	        // 换言之，i 之前被 pri_j 筛过了
	        // 由于 pri 里面质数是从小到大的,所以 i 乘上其他的质数的结果一定会被
	        // pri_j 的倍数筛掉,就不需要在这里先筛一次,所以这里直接 break
		}  
	}
}

参考博客：

筛法 - OI Wiki (oi-wiki.org)