Hướng dẫn giải của SANGNT01: Liệt kê số 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
Liệt kê các số nguyên tố không vượt quá N (N ≤ 10^7). Với N lớn, phải dùng sàng để tránh kiểm tra từng số.
Sub 1: Thử chia từng số — ~O(n \sqrt{n})~
Với mỗi số i từ 2 đến N, thử chia cho các số j từ 2 đến căn của i. Đúng nhưng chậm khi N lớn. Đạt 16/20 test, 4 test còn lại quá giờ.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
// Vét cạn: thử chia i cho mọi j từ 2 đến căn(i)
for (long long i = 2; i <= n; i++) {
bool prime = true;
for (long long j = 2; j * j <= i; j++)
if (i % j == 0) { prime = false; break; }
if (prime) cout << i << " ";
}
cout << "\n";
return 0;
}
Sub 2: Sàng Eratosthenes — ~O(n \log \log n)~
Đánh dấu hợp số: khi gặp số nguyên tố i thì đánh dấu các bội của i bắt đầu từ i·i (các bội nhỏ hơn đã được số nhỏ hơn đánh dấu). Dùng long long khi tính i·i để tránh tràn số. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// Sàng Eratosthenes: đánh dấu bội của mỗi số nguyên tố là hợp số
vector<char> composite(n + 1, 0);
string out;
for (int i = 2; i <= n; i++) {
if (composite[i]) continue;
out += to_string(i);
out += ' ';
// Đánh dấu từ i*i vì các bội nhỏ hơn đã được đánh dấu bởi số nhỏ hơn
for (long long j = (long long)i * i; j <= n; j += i)
composite[j] = 1;
}
out += '\n';
cout << out;
return 0;
}
Bình luận