Hướng dẫn giải của SANGNT03: Tổng nguyên tố
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 số nguyên dương N (N <= 10^7), tính tổng các số nguyên tố nhỏ hơn hoặc bằng N. 20% số test có N <= 10^3.
Sub 1: Thử chia từng số — ~O(N \sqrt{N})~, dùng khi ~N \le 1000~
Với mỗi số từ 2 đến N, thử chia đến căn bậc hai để kiểm tra nguyên tố rồi cộng dồn.
Nếu chỉ nộp sub này: đúng 17/20 test (các test N lớn bị quá giờ).
Sub 2: Sàng Eratosthenes — ~O(N \log \log N)~
Đánh dấu hợp số bằng sàng, mỗi số chưa bị đánh dấu là nguyên tố và được cộng vào tổng. Bẫy: tổng có thể lên khoảng 3·10^12 nên dùng long long.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc N. Nếu N <= 1000 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long N;
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 tung so tu 2 den N, O(N * sqrt(N)) — dung khi N <= 1000
void sub1() {
long long s = 0;
for (long long i = 2; i <= N; i++)
if (isPrimeTrial(i)) s += i;
cout << s << "\n";
}
// Sub 2: sang Eratosthenes den N, cong tong cac so nguyen to
void sub2() {
vector<bool> comp(N + 1, false);
long long s = 0;
for (long long i = 2; i <= N; i++) {
if (comp[i]) continue;
s += i;
for (long long j = i * i; j <= N; j += i) comp[j] = true;
}
cout << s << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
if (N <= 1000) sub1();
else sub2();
return 0;
}
Bình luận