Hướng dẫn giải của F11: 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
Cho số nguyên dương N (có thể tới 10^18). Tính tổng các chữ số K của N, rồi kiểm tra K có phải số nguyên tố hay không. In Yes nếu K là số nguyên tố, ngược lại in No.
Cách làm
Vì N lên tới 10^18 nên phải dùng kiểu long long. Lấy lần lượt chữ số cuối bằng phép chia lấy dư cho 10 và cộng dồn vào K, sau đó chia N cho 10 cho tới khi N bằng 0. Tổng K nhiều nhất khoảng 171 nên việc kiểm tra số nguyên tố rất nhanh.
#include <bits/stdc++.h>
using namespace std;
// Kiểm tra số k có phải số nguyên tố hay không
bool la_nguyen_to(long long k) {
if (k < 2) {
return false;
}
for (long long i = 2; i * i <= k; i++) {
if (k % i == 0) {
return false;
}
}
return true;
}
int main() {
// N có thể lên tới 10^18 nên dùng long long
long long n;
cin >> n;
// Tính tổng các chữ số của N (tối đa khoảng 171, rất nhỏ)
long long k = 0;
long long tam = n;
while (tam > 0) {
k += tam % 10;
tam = tam / 10;
}
if (la_nguyen_to(k)) {
cout << "Yes\n";
} else {
cout << "No\n";
}
return 0;
}
Bình luận