数学算法

Amroning / 2024-11-26 / 原文

1.筛质数

力扣相关题目：204. 计数质数、2523. 范围内最接近的两个质数

要在某个范围内计算出所有质数时，先在这个范围内做预处理，把所有的质数筛出来

埃氏筛：从前往后，把质数的倍数都去掉（因为这肯定不是质数了）

const int MX = 5e6;			//比如数据范围是0~5*10^6
vector<int>primes;			//保存质数的数组

int init = []() {
	bool nums[MX + 1]{};		//bool数组标记质数和非质数，false为质数，true为合数
	for (int i = 2; i <= MX; ++i) {		//刚开始从2开始，肯定是质数
		if (!nums[i])
			primes.push_back(i);
		for (int j = i; j <= MX / i; ++j)	//质数的倍数都是合数，标记为true
			nums[i * j] = true;
	}

	primes.push_back(MX + 1);		//依题目而定是否要在最后插入这两个数，可以在相关题目中省去判断下标是否越界
	primes.push_back(MX + 1);

	return 0;
}();

欧拉筛：每一个合数只用它最小的质因子筛掉

const int MX = 1e6;
vector<int>primes;

int init = []() {
	bool nums[MX + 1]{};
	for (int i = 2; i <= MX; ++i) {
		if (!nums[i])
			primes.push_back(i);
		for (int n : primes) {
			if (n > MX / i)
				break;
			nums[n * i] = true;
			if (!(i % n))		//每个合数只会被筛一次，只被它的最小的质因子筛掉
				break;
		}
	}

	primes.push_back(MX + 1);
	primes.push_back(MX + 1);
	
	return 0;
}();