2022.7.4筛法代码
作者:
该训练了
,
2022-07-04 20:35:51
,
所有人可见
,
阅读 152
/*
Author: SJ
Think twice, code once.
*/
#include <bits/stdc++.h>
const int N = 1e6 + 10;
using ll = long long;
int n, cnt;
std::vector<int> prime_list;
bool isnp[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
for (int i = 2; i <= n; i++) {
if (!isnp[i]) {
for (int j = i; j <= n; j += i) isnp[j] = true;
prime_list.push_back(i);
cnt++;
}
}
std::cout << cnt;
return 0;
}
埃氏筛
/*
Author: SJ
Think twice, code once.
*/
#include <bits/stdc++.h>
const int N = 1e6 + 10;
using ll = long long;
int n, cnt;
std::vector<int> prime_list;
bool isnp[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
for (int i = 2; i <= n; i++) {
if (!isnp[i]) {
prime_list.push_back(i);
cnt++;
}
for (int j : prime_list) {
if (i * j > n) break;
isnp[i * j] = true;
if (i % j == 0) break;
}
}
std::cout << cnt;
return 0;
}
欧筛