Hướng dẫn giải của Cặp số nguyên tố (Đề chọn ĐTQG Phú Thọ 2014-2015)
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
Cho n và k (2 <= k < n <= 10^6), đếm số cặp số nguyên tố (x, y) với x < y < n và y - x = k. Nếu không có cặp nào thì in -1. Đề dùng file CAU4.INP và CAU4.OUT.
Sub 1: Thử chia từng số — ~O(n \sqrt{n})~, dùng khi ~n \le 2000~
Với mỗi x sao cho x + k < n, kiểm tra x và x + k đều là số nguyên tố bằng thử chia.
Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Sàng Eratosthenes — ~O(n \log \log n)~
Sàng các số đến n, rồi đếm x sao cho x và x + k đều không bị đánh dấu hợp số. Bẫy: điều kiện là x + k < n (strict) và in -1 khi không có cặp nào.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc n, k từ CAU4.INP. Nếu n <= 2000 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long n, k;
bool isPrimeTrial(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: thu chia kiem tra nguyen to tung cap (x, x+k) voi x+k < n — dung khi n <= 2000
void sub1() {
long long cnt = 0;
for (long long x = 2; x + k < n; x++)
if (isPrimeTrial(x) && isPrimeTrial(x + k)) cnt++;
cout << (cnt > 0 ? cnt : -1) << "\n";
}
// Sub 2: sang Eratosthenes den n, roi kiem tra tung cap (x, x+k)
void sub2() {
vector<bool> comp(n + 1, false);
comp[0] = true;
comp[1] = true;
for (long long i = 2; i * i <= n; i++)
if (!comp[i])
for (long long j = i * i; j <= n; j += i) comp[j] = true;
long long cnt = 0;
for (long long x = 2; x + k < n; x++)
if (!comp[x] && !comp[x + k]) cnt++;
cout << (cnt > 0 ? cnt : -1) << "\n";
}
int main() {
freopen("CAU4.INP", "r", stdin);
freopen("CAU4.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
if (n <= 2000) sub1();
else sub2();
return 0;
}
Bình luận