Hướng dẫn giải của Số nguyên tố (đề Daknong 2021)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Liệt kê các số nguyên tố n trong khoảng (p, 2p) và đếm chúng.
Sub 1: Vét cạn, ~O(p \sqrt{2p})~ (p ≤ 10^4)
Kiểm tra mỗi n bằng chia thử. Đúng 20/20 test.
Sub 2: Sàng Eratosthenes, ~O(p \log \log p)~
Sàng đến 2p rồi lấy các số không phải hợp số trong (p, 2p). Đúng 20/20 test.
Chương trình hoàn chỉnh
main: p ≤ 10^4 gọi sub1, còn lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
long long p;
// Kiem tra x co phai so nguyen to khong (chia thu)
bool isPrime(long long x) {
if (x < 2) return false;
for (long long d = 2; d * d <= x; d++)
if (x % d == 0) return false;
return true;
}
// Sub 1: vet can. Voi moi n trong khoang (p, 2p), kiem tra n co la so nguyen to bang chia thu.
void sub1() {
vector<long long> res;
for (long long n = p + 1; n < 2 * p; n++)
if (isPrime(n)) res.push_back(n);
for (size_t i = 0; i < res.size(); i++) cout << res[i] << (i + 1 < res.size() ? " " : "");
cout << "\n" << res.size() << "\n";
}
// Sub 2: sang Eratosthenes tren doan [0, 2p] de biet ngay cac so nguyen to, roi lay cac so trong (p, 2p).
void sub2() {
int M = 2 * p;
vector<bool> comp(M + 1, false);
comp[0] = true;
if (M >= 1) comp[1] = true;
for (int i = 2; (long long)i * i <= M; i++)
if (!comp[i])
for (int j = i * i; j <= M; j += i) comp[j] = true;
vector<long long> res;
for (long long n = p + 1; n < 2 * p; n++)
if (!comp[n]) res.push_back(n);
for (size_t i = 0; i < res.size(); i++) cout << res[i] << (i + 1 < res.size() ? " " : "");
cout << "\n" << res.size() << "\n";
}
int main() {
freopen("bertran.inp", "r", stdin);
freopen("bertran.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> p;
if (p <= 10000) sub1();
else sub2();
return 0;
}
Bình luận