Hướng dẫn giải của F06: Tính nguyên tố của số ước
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
Đếm số ước K của N (N <= 10^9), rồi kiểm tra K có phải số nguyên tố không. Đưa ra True hoặc False.
Sub 1: Thử mọi số từ 1 đến N để đếm ước — ~O(N)~
Với mỗi i từ 1 đến N, nếu N chia hết cho i thì tăng bộ đếm. Đúng nhưng N đến 10^9 nên quá chậm với nhiều test: 11 test bị TLE.
Kết quả chấm: đạt 9/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
// Vet can: thu tung so i tu 1 den n, dem so uoc
long long k = 0;
for (long long i = 1; i <= n; i++)
if (n % i == 0) k++;
bool prime = (k >= 2);
for (long long i = 2; i * i <= k; i++)
if (k % i == 0) { prime = false; break; }
cout << (prime ? "True" : "False") << endl;
return 0;
}
Sub 2: Chỉ thử i đến căn bậc hai của N — ~O(sqrt(N))~
Các ước đi theo cặp (i, N/i) nên chỉ cần thử i đến sqrt(N). Nếu ii = N thì chỉ tính một ước, nếu không thì tính hai ước. Sau đó kiểm tra K nguyên tố bằng cách thử chia đến sqrt(K), với K <= 1344 khi N <= 10^9. Bẫy: dùng long long khi tính ii.
Kết quả chấm: đạ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;
// Uoc i va n/i luon xuat hien theo cap, chi can xet i <= sqrt(n)
long long k = 0;
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
if (i * i == n) k += 1; // uoc can bang nhau (n la so chinh phuong)
else k += 2; // hai uoc i va n/i
}
}
// Kiem tra k co phai so nguyen to khong (k <= 1344 voi n <= 1e9)
bool prime = (k >= 2);
for (long long i = 2; i * i <= k; i++)
if (k % i == 0) { prime = false; break; }
cout << (prime ? "True" : "False") << endl;
return 0;
}
Bình luận