Hướng dẫn giải của LOOP17: 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
Kiểm tra N có đúng hai ước là 1 và N hay không (N = 1 không phải số nguyên tố). N ≤ 2·10^9 nên không thể thử đến N.
Sub 1: Vét cạn — ~O(N)~
Thử chia N cho mọi số từ 2 đến N − 1. Đạt 17/20 test (3 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 N cho mọi số từ 2 đến N-1
bool prime = n >= 2;
for (long long i = 2; i < n; i++)
if (n % i == 0) { prime = false; break; }
cout << (prime ? "Yes" : "No") << "\n";
return 0;
}
Sub 2: Thử đến căn bậc hai — ~O(√N)~
Nếu N có ước d với 1 < d < N thì N có ước N/d, và trong hai ước này có một ước không vượt √N, nên chỉ cần thử d đến √N. Với N ≤ 2·10^9, √N ≈ 44722 nên chạy rất nhanh. Lưu ý dùng biến long long khi tính i·i. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
bool prime = n >= 2;
// Nếu N có ước d thì luôn có ước N/d, nên chỉ cần thử d <= căn(N)
for (long long i = 2; i * i <= n; i++)
if (n % i == 0) { prime = false; break; }
cout << (prime ? "Yes" : "No") << "\n";
return 0;
}
Bình luận