质数筛

枚举法

暴力枚举法， 一般在查询很少的时候使用

判断一个数 n 是否为质数的时间复杂度为\(O(\sqrt{n})\)

若询问m次，时间复杂度为 \(O(m\sqrt{n})\)

bool isPrime(int x){
	if(x < 2) return false;
	for(int i = 2 ; i*i <= x ; i ++){
		if(x % i == 0) return false;
	}
	return true;
}

埃式筛法

Eratosthenes 筛法（埃拉托斯特尼筛法，简称埃氏筛法。

建立一个<=n的\(O(1)\)查询表的时间复杂度是\(O(nloglogn)\)

原理：对于任意一个大于1的正整数，那么它的x倍就是非素数。如果从小到大遍历每个数，同时把当前数的所有倍数记为非素数，那么运行结束的时候没有被标记的数就是素数了。

vector<bool> isPrime;
void initPrime(int n){
	isPrime.resize(n+1, true);
	isPrime[0] = isPrime[1] = false;
	for(int i = 2 ; i <= n ; i ++){ 
		if(isPrime[i]){
			for(int j = i*i ; j <= n ; j += i){
                // 注意这里可以从i*i开始,而不是2*i
                // 因为所有因数为 [2, i-1] 的乘积都已经被计算过；
				isPrime[j] = false;
			}
		}
	}
}

欧拉筛法

埃氏筛法仍有优化空间，它会将一个合数重复多次标记。

而欧拉筛法保证了一个合数只被最小的素因数标记，达到了线性的时间复杂度

建立一个<=n的\(O(1)\)查询表的时间复杂度是\(O(n)\)

原理：从小到大遍历每个数，记录<= i的非素数，将它们与 i 的乘积（<=n）标记为非素数，若i % it == 0，则直接break，因为后面还会有更大倍数标记这个乘积。

vector<bool> isPrime;
void initPrime(int n){
	isPrime.resize(n+1, true);
	isPrime[0] = isPrime[1] = false;
    vector<int > pri;
	for(int i = 2 ; i <= n ; i ++){
		if(isPrime[i]){
			pri.push_back(i);
		}
		for(auto it : pri){
			if(i*it > n) break;
			isPrime[i*it] = false;
			if(i % it == 0) break; //关键
		}
	}
}