Hướng dẫn giải của Đếm số (THCS KS1)
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 một xâu gồm chữ số, chữ cái thường và chữ cái hoa (độ dài tới 10^6). Đếm số lượng số nguyên tố có một chữ số xuất hiện trong xâu. Các số nguyên tố một chữ số là 2, 3, 5, 7.
Sub 1: Vét cạn, kiểm tra từng ký tự — ~O(n)~
Duyệt từng ký tự, nếu là chữ số thì kiểm tra số đó có phải số nguyên tố bằng cách thử các ước. Mọi chữ số 0..9 đều được kiểm tra nên đúng với mọi test.
Kết quả chấm: 20/20 (SUB ok 20/20, TLE 0, WA 0)
#include <bits/stdc++.h>
using namespace std;
// Kiem tra mot chu so (0..9) co phai so nguyen to khong bang cach thu uoc
bool laNguyenTo(int x) {
if (x < 2) return false;
for (int d = 2; d < x; d++)
if (x % d == 0) return false;
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int dem = 0;
// Vet can: voi moi ky tu, neu la chu so thi kiem tra xem co phai so nguyen to khong
for (char c : s)
if (isdigit(c) && laNguyenTo(c - '0')) dem++;
cout << dem << "\n";
return 0;
}
Sub 2: Liệt kê trực tiếp bốn chữ số nguyên tố — ~O(n)~
Chỉ cần đếm các ký tự thuộc tập {'2', '3', '5', '7'}. Không cần kiểm tra nguyên tố lại cho từng ký tự.
Bẫy: chữ cái không phải chữ số nên không được tính, dù có các chữ như 'a' hay 'Z' cũng bỏ qua.
Kết quả chấm: 20/20
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
// Cac so nguyen to co mot chu so la 2, 3, 5, 7: dem cac ky tu thuoc bo nay
int dem = 0;
for (char c : s)
if (c == '2' || c == '3' || c == '5' || c == '7') dem++;
cout << dem << "\n";
return 0;
}
Bình luận