Hướng dẫn giải của F05: Tổng nguyên tố 2
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
Tính tổng các số nguyên tố nhỏ hơn hoặc bằng ~N~, với ~N \le 10^7~.
Sub 1: kiểm tra từng số — ~O(N \sqrt{N})~, dùng khi ~N \le 10^5~
Với mỗi số từ 2 đến ~N~, thử chia cho các số đến căn bậc hai. Nếu chỉ nộp sub này: đúng 14/20 test.
Sub 2: sàng Eratosthenes — ~O(N \log \log N)~
Dùng mảng đánh dấu để sàng các hợp số, cộng dần các số nguyên tố. Đúng 20/20 test. Tổng có thể vượt 2^31, dùng long long.
Chương trình hoàn chỉnh
main đọc N. Nếu ~N \le 10^5~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
// Tong cac so nguyen to <= N.
// Sub 1: kiem tra tung so tu 2 den N bang cach thu chia cac uoc nho hon can bac hai.
// Dung khi N <= 10^5.
long long sub1(long long N) {
long long sum = 0;
for (long long x = 2; x <= N; x++) {
bool prime = true;
for (long long d = 2; d * d <= x; d++)
if (x % d == 0) { prime = false; break; }
if (prime) sum += x;
}
return sum;
}
// Sub 2: sang Eratosthenes, O(N log log N). Dung cho N lon.
long long sub2(long long N) {
vector<bool> isPrime(N + 1, true);
long long sum = 0;
for (long long i = 2; i <= N; i++) {
if (!isPrime[i]) continue;
sum += i;
for (long long j = i * i; j <= N; j += i) isPrime[j] = false;
}
return sum;
}
int main() {
long long N;
cin >> N;
long long ans = (N <= 100000) ? sub1(N) : sub2(N);
cout << ans << "\n";
return 0;
}
Bình luận