算法笔记

Appearance

数论筛法 ​

Euler 筛 ​

cpp
std::vector<bool> isp;
std::vector<int> primes;
void euler(int n) {
	isp.resize(n + 1, true);
	for (int i = 2; i <= n; i++) {
		if (isp[i])
			primes.push_back(i);
		for (int pj : primes) {
			if (pj > n / i)
				break;
			isp[i * pj] = false;
			if (i % pj == 0)
				break;
		}
	}
}

Euler 筛・LPF ​

cpp
std::vector<int> lpf, primes;
void Euler(int n) {
	lpf.resize(n + 1);
	for (int i = 2; i <= n; i++) {
		if (!lpf[i])
			lpf[i] = i, primes.push_back(i);
		for (auto pj : primes) {
			if (pj > n / i)
				break;
			lpf[i * pj] = pj;
			if (i % pj == 0)
				break;
		}
	}
}

Eratosthenes 筛 ​

cpp
std::vector<bool> isp;
std::vector<int> primes;
void Eratosthenes(int n) {
	isp.resize(n + 1, true);
	for (int i = 2; i <= n; i++) {
		if (isp[i]) {
			primes.push_back(i);
			for (i64 j = i64(i) * i; j <= n; j += i)
				isp[j] = false;
		}
	}
}