今天我刷题了吗
搜索文档…
筛法

欧拉筛法

1
void euler(int n, vector<int>& primes)
2
{
3
primes.clear();
4
vector<bool> isPrime(n + 1, true);
5
isPrime[0] = isPrime[1] = false;
6
for (int i = 2; i <= n; i++) {
7
if (isPrime[i]) {
8
primes.push_back(i);
9
}
10
for (int p : primes) {
11
if (1ll * i * p > n) break;
12
isPrime[i * p] = false;
13
if (i % p == 0) break;
14
}
15
}
16
}
Copied!

埃拉托斯特尼筛法

1
void eratosthenes(int n, vector<int>& primes)
2
{
3
primes.clear();
4
vector<bool> isPrime(n + 1, true);
5
isPrime[0] = isPrime[1] = false;
6
for (int i = 2; i <= n; i++) {
7
if (!isPrime[i]) continue;
8
primes.push_back(i);
9
if (ll(i) * i > n) continue;
10
for (int j = i * i; j <= n; j += i) {
11
isPrime[j] = false;
12
}
13
}
14
}
Copied!
最近更新 1yr ago
复制链接