Hướng dẫn giải của Không nguyên tố (Minh họa TS chuyên PT 2024)
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
Đếm trong đoạn ~[L, R]~ các số không phải số nguyên tố. Số 1 không phải số nguyên tố nên được tính.
Sub 1: Vét cạn — ~O((R - L) \cdot R)~, dùng khi ~R \le 1000~
Với mỗi ~x~ trong đoạn, thử chia cho mọi số từ 2 đến ~x-1~. Nếu không có ước nào thì ~x~ là số nguyên tố, ngược lại thì tăng bộ đếm. Số 1 được xếp vào "không nguyên tố". Nếu chỉ nộp sub này: đúng 10/20 test (đúng hết các test trong miền, 10 test lớn bị quá giờ).
Sub 2: Sàng Eratosthenes — ~O(R \log \log R)~, dùng cho ~R \le 10^6~
Đánh dấu hợp số trong ~[0, R]~ bằng sàng: với mỗi ~i~ chưa bị đánh dấu, đánh dấu các bội từ ~i^2~ trở đi. Sau đó đếm các ~x \in [L, R]~ bị đánh dấu (kể cả số 1).
Bẫy cần chú ý: đánh dấu 0 và 1 là không nguyên tố; dùng long long cho ~i \cdot i~ để tránh tràn số.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc ~L, R~. Nếu ~R \le 1000~ thì gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long L, R;
// Sub 1: vet can - voi moi x trong [L, R], thu chia cho moi so tu 2 den x-1. Dung khi R <= 1000.
void sub1() {
long long cnt = 0;
for (long long x = L; x <= R; x++) {
bool prime = (x >= 2);
for (long long d = 2; d < x && prime; d++)
if (x % d == 0) prime = false;
if (!prime) cnt++; // gom ca so 1 (khong phai so nguyen to)
}
cout << cnt << "\n";
}
// Sub 2: sang Eratosthenes tren [0, R], sau do dem so khong nguyen to trong [L, R]
void sub2() {
vector<bool> composite(R + 1, false);
composite[0] = true;
if (R >= 1) composite[1] = true; // so 1 khong phai nguyen to
for (long long i = 2; i * i <= R; i++)
if (!composite[i])
for (long long j = i * i; j <= R; j += i)
composite[j] = true;
long long cnt = 0;
for (long long x = L; x <= R; x++)
if (composite[x]) cnt++;
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> L >> R;
if (R <= 1000) sub1(); // du lieu nho: vet can
else sub2(); // du lieu lon: sang
return 0;
}
Bình luận