Hướng dẫn giải của Tin 10 Bài 8: 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
Số nguyên tố là số có đúng 2 ước (1 và chính nó). Với ba số dương A, B, C nhập trên một dòng, cần in TRUE hoặc FALSE cho từng số theo thứ tự, cách nhau bởi dấu cách.
Sub 1: Đếm đủ các ước — ~O(N)~
Với mỗi số, thử mọi d từ 1 đến N và đếm số ước. Nếu đếm được đúng 2 ước thì là số nguyên tố. Cách này trực tiếp theo định nghĩa nhưng chậm với số lớn.
Kết quả chấm: đạt 16/20 test, 4 test quá thời gian, không sai test nào.
#include <bits/stdc++.h>
using namespace std;
// Vét cạn: đếm số ước của x bằng cách thử mọi d từ 1 đến x
bool laSoNguyenTo(long long x) {
int dem = 0;
for (long long d = 1; d <= x; d++)
if (x % d == 0) dem++;
return dem == 2; // đúng 2 ước (1 và chính nó)
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b, c;
cin >> a >> b >> c;
cout << (laSoNguyenTo(a) ? "TRUE" : "FALSE") << " "
<< (laSoNguyenTo(b) ? "TRUE" : "FALSE") << " "
<< (laSoNguyenTo(c) ? "TRUE" : "FALSE") << "\n";
return 0;
}
Sub 2: Chỉ thử ước đến căn bậc hai — ~O(\sqrt{N})~
Nếu N có ước d với 2 ≤ d ≤ √N thì N không phải số nguyên tố; ngược lại N là số nguyên tố. Lưu ý số 1 không phải số nguyên tố nên trả về FALSE.
Kết quả chấm: đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
// Kiểm tra x có phải số nguyên tố: chỉ cần thử các ước d đến căn x
bool laSoNguyenTo(long long x) {
if (x < 2) return false; // 1 không phải số nguyên tố
for (long long d = 2; d * d <= x; d++)
if (x % d == 0) return false; // có ước khác 1 và chính nó
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long a, b, c;
cin >> a >> b >> c;
cout << (laSoNguyenTo(a) ? "TRUE" : "FALSE") << " "
<< (laSoNguyenTo(b) ? "TRUE" : "FALSE") << " "
<< (laSoNguyenTo(c) ? "TRUE" : "FALSE") << "\n";
return 0;
}
Bình luận