当前位置：首页 > news >正文

埃式筛法欧拉筛法质数分布定理

news 2025/8/18 5:39:46

埃拉托斯特尼筛法

时间复杂度O（nloglogn）

保证每个合数都会被筛出：每个合数必能分解出质数，从而一定会被筛出

不能保证每个合数只会被筛一遍（时间复杂度控制）：每个合数可能被多个较小质因数筛出，如120会被2，3，5重复筛选，造成时间浪费（这点不如欧拉筛，欧拉筛不会重复筛选）

题目：P3383 【模板】线性筛素数 - 洛谷

code

注意：先将p * i标记为素数，再if (i % p == 0) break;

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;vector<int> primes;
vector<bool> vis = vector<bool>(1e8 + 7, false);void ola(int n)
{for (int i = 2; i <= n; i++){if (!vis[i])primes.push_back(i);for (int p : primes){if (p * i > n) break;vis[p * i] = true;if (i % p == 0) break;}}
}int main()
{int n, q; cin >> n >> q;ola(n);while (q--){int k; cin >> k;cout << primes[k - 1] << endl;}return 0;
}

欧拉筛法

时间复杂度：O（N）

核心思想:让每一个合数被其最小质因数筛到。
所以,我们不需要用一个for循环去筛除一个质数的所有倍数,我们将所有质数存储到primes[]中,然后枚举到第i个数时,就筛去所有的primes[j]*i。这样就在每一次遍历中,正好筛除了所有已知素数的i倍。
但是为了确保合数只被最小质因子筛掉,最小质因子要乘以最大的倍数,即要乘以最大的i,所以不能提前筛,所以如果i% primes[j] == 0,我们就结束内层循环!

题目：P3912 素数个数 - 洛谷

code

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;const int _max = int(1e8 + 7);
long long ans = 0;
bool isprime[_max];void ai(int N)
{memset(isprime, true, sizeof(isprime));for (int i = 2; i <= N / i; i++){if (!isprime[i]){continue;}for (int j = i + i; j <= N; j += i){isprime[j] = false;}}
}int main()
{int N; cin >> N;ai(N);for (int i = 2; i <= N; i++) if (isprime[i]) ans++;cout << ans << endl;return 0;
}