Số nguyên tố
Số nguyên tố là chủ đề xuất hiện nhiều nhất trong đề thi học sinh giỏi Tin học: kiểm tra số nguyên tố, đếm số nguyên tố, phân tích thừa số nguyên tố, số siêu nguyên tố… Bài này dùng lại ý “ước đi theo cặp” của bài Ước và bội, các bạn nên học bài đó trước.
Số nguyên tố là gì?
Phần tiêu đề “Số nguyên tố là gì?”Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có đúng hai ước: 1 và chính nó. Các số nguyên tố đầu tiên là 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …
- 1 không phải số nguyên tố (chỉ có một ước).
- 2 là số nguyên tố chẵn duy nhất: mọi số chẵn khác đều chia hết cho 2.
- Số lớn hơn 1 mà không phải số nguyên tố gọi là hợp số, ví dụ 4, 6, 9, 91.
Kiểm tra số nguyên tố
Phần tiêu đề “Kiểm tra số nguyên tố”Muốn biết n có phải số nguyên tố không, ta tìm xem n có ước nào từ 2 đến n - 1 hay không. Nhưng không cần thử hết: theo bài Ước và bội, nếu n = a × b với a ≤ b thì a ≤ √n. Vậy nếu n có ước (khác 1 và n) thì chắc chắn có một ước không vượt quá √n. Chỉ cần thử d từ 2 đến √n.
| n | Thử d = 2, 3, … với d × d ≤ n | Kết luận |
|---|---|---|
| 91 | 2, 3, 4, 5, 6 không chia hết; 91 = 7 × 13 | hợp số |
| 97 | 2, 3, …, 9 đều không chia hết (10 × 10 = 100 > 97) | nguyên tố |
def la_nguyen_to(n): if n < 2: return False # 0 và 1 không phải số nguyên tố d = 2 while d * d <= n: if n % d == 0: return False # tìm được ước, là hợp số d += 1 return True
print(la_nguyen_to(91), la_nguyen_to(97)) # False True#include <iostream>using namespace std;
bool laNguyenTo(long long n) { if (n < 2) return false; // 0 và 1 không phải số nguyên tố for (long long d = 2; d * d <= n; d++) { if (n % d == 0) return false; // tìm được ước, là hợp số } return true;}
int main() { cout << laNguyenTo(91) << " " << laNguyenTo(97) << endl; // 0 1 return 0;}Với n tới 1012, vòng lặp chạy nhiều nhất 106 lần, rất nhanh.
Lưu ý: nhớ trường hợp n = 0 và n = 1. Thiếu dòng if n < 2 thì vòng lặp không
chạy lần nào và hàm trả về True, coi 1 là số nguyên tố.
Nhanh gấp đôi: sau khi thử d = 2, chỉ cần thử các số lẻ 3, 5, 7, … vì nếu n không chia hết cho 2 thì cũng không chia hết cho số chẵn nào.
Phân tích thừa số nguyên tố
Phần tiêu đề “Phân tích thừa số nguyên tố”Mọi số lớn hơn 1 đều viết được thành tích các số nguyên tố, và chỉ có một cách viết (không kể thứ tự). Ví dụ 360 = 23 × 32 × 5.
Cách làm: thử d = 2, 3, 4, … Gặp d mà n chia hết cho d thì chia n cho d nhiều lần nhất có thể, đếm số lần chia. Chạy tay với 360:
| d | Chia liên tiếp | Số lần | n còn lại |
|---|---|---|---|
| 2 | 360 → 180 → 90 → 45 | 3 | 45 |
| 3 | 45 → 15 → 5 | 2 | 5 |
| 4 | 4 × 4 > 5, dừng | 5 |
Sau vòng lặp n còn 5 (lớn hơn 1) nên 5 là thừa số nguyên tố cuối cùng. Kết quả 360 = 23 × 32 × 5.
Vì sao d = 4 không bao giờ chia hết? Vì lúc tới d = 4, mọi thừa số 2 đã bị chia hết ra rồi. Nên mỗi khi n chia hết cho d thì d chắc chắn là số nguyên tố, không cần kiểm tra.
n = int(input())d = 2while d * d <= n: so_mu = 0 while n % d == 0: n //= d so_mu += 1 if so_mu > 0: print(d, so_mu) # thừa số d với số mũ so_mu d += 1if n > 1: print(n, 1) # phần còn lại là một số nguyên tố#include <iostream>using namespace std;
int main() { long long n; cin >> n; for (long long d = 2; d * d <= n; d++) { int soMu = 0; while (n % d == 0) { n /= d; soMu++; } if (soMu > 0) cout << d << " " << soMu << endl; // thừa số d với số mũ soMu } if (n > 1) cout << n << " " << 1 << endl; // phần còn lại là một số nguyên tố return 0;}Lưu ý: điều kiện vòng lặp d * d <= n dùng n đang giảm dần, nên vòng lặp
dừng sớm. Đừng quên phần if n > 1 ở cuối: với n = 26 = 2 × 13, sau khi chia n cho 2
thì n = 13, vòng lặp dừng ở d = 4 và 13 chỉ được in ra nhờ dòng này.
Đếm ước từ phân tích thừa số
Phần tiêu đề “Đếm ước từ phân tích thừa số”Mỗi ước của 360 = 23 × 32 × 5 có dạng 2a × 3b × 5c, trong đó:
- a chọn từ 0 đến 3: 4 cách,
- b chọn từ 0 đến 2: 3 cách,
- c chọn từ 0 đến 1: 2 cách.
Số ước là 4 × 3 × 2 = 24. Quy tắc chung: cộng 1 vào mỗi số mũ rồi nhân lại.
Số chữ số 0 tận cùng của n!
Phần tiêu đề “Số chữ số 0 tận cùng của n!”n! (đọc là n giai thừa) là tích 1 × 2 × 3 × … × n. Mỗi chữ số 0 tận cùng ứng với một thừa số 10 = 2 × 5. Thừa số 2 luôn nhiều hơn thừa số 5, nên số chữ số 0 tận cùng bằng số thừa số 5 trong n!.
Đếm thừa số 5 trong 100!:
- Các số chia hết cho 5 (5, 10, …, 100) góp mỗi số một thừa số 5: 100 // 5 = 20.
- Các số chia hết cho 25 (25, 50, 75, 100) góp thêm một thừa số 5 nữa: 100 // 25 = 4.
- 125 > 100, dừng.
100! có 20 + 4 = 24 chữ số 0 tận cùng, tính được mà không cần nhân ra số có 158 chữ số.
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 21 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.
Nhóm 1. Kiểm tra số nguyên tố
Phần tiêu đề “Nhóm 1. Kiểm tra số nguyên tố”Bài 1. Kiểm tra số nguyên tố
Phần tiêu đề “Bài 1. Kiểm tra số nguyên tố”Nhập số nguyên n (0 ≤ n ≤ 1012). In ra YES nếu n là số nguyên tố, ngược lại in ra NO.
Ví dụ: nhập 97 thì in ra YES.
Kiểm tra: nhập 1000000007.
Bài 2. Số nguyên tố tiếp theo
Phần tiêu đề “Bài 2. Số nguyên tố tiếp theo”Nhập số nguyên dương n (n ≤ 1012). In ra số nguyên tố nhỏ nhất lớn hơn hoặc bằng n.
Ví dụ: nhập 20 thì in ra 23.
Kiểm tra: nhập 1000000.
Bài 3. Số nguyên tố lớn nhất không vượt quá n
Phần tiêu đề “Bài 3. Số nguyên tố lớn nhất không vượt quá n”Nhập số nguyên n (2 ≤ n ≤ 1012). In ra số nguyên tố lớn nhất nhỏ hơn hoặc bằng n.
Ví dụ: nhập 20 thì in ra 19.
Kiểm tra: nhập 1000000000000.
Bài 4. Liệt kê số nguyên tố
Phần tiêu đề “Bài 4. Liệt kê số nguyên tố”Nhập số nguyên dương n (n ≤ 104). In ra các số nguyên tố không vượt quá n theo thứ tự tăng dần, cách nhau một dấu cách. Nếu không có số nào thì in ra 0.
Ví dụ: nhập 20 thì in ra 2 3 5 7 11 13 17 19.
Kiểm tra: nhập 50.
Bài 5. Đếm số nguyên tố trong đoạn
Phần tiêu đề “Bài 5. Đếm số nguyên tố trong đoạn”Nhập hai số nguyên a, b (1 ≤ a ≤ b ≤ 105). In ra số lượng số nguyên tố trong đoạn từ a đến b.
Ví dụ: nhập 1 20 thì in ra 8.
Kiểm tra: nhập 100 1000.
Bài 6. Tổng các số nguyên tố
Phần tiêu đề “Bài 6. Tổng các số nguyên tố”Nhập số nguyên dương n (n ≤ 105). In ra tổng các số nguyên tố không vượt quá n.
Ví dụ: nhập 10 thì in ra 17.
Kiểm tra: nhập 1000.
Nhóm 2. Phân tích thừa số nguyên tố
Phần tiêu đề “Nhóm 2. Phân tích thừa số nguyên tố”Bài 7. Phân tích thừa số nguyên tố
Phần tiêu đề “Bài 7. Phân tích thừa số nguyên tố”Nhập số nguyên n (2 ≤ n ≤ 1012). In ra phân tích thừa số nguyên tố của n theo dạng: các thừa số tăng dần, nối bằng dấu *, thừa số có số mũ lớn hơn 1 viết p^k. Ví dụ 360 viết là 2^3*3^2*5.
Ví dụ: nhập 360 thì in ra 2^3*3^2*5.
Kiểm tra: nhập 1001000.
Bài 8. Ước nguyên tố lớn nhất
Phần tiêu đề “Bài 8. Ước nguyên tố lớn nhất”Nhập số nguyên n (2 ≤ n ≤ 1012). In ra ước nguyên tố lớn nhất của n.
Ví dụ: nhập 360 thì in ra 5.
Kiểm tra: nhập 123456789.
Bài 9. Số ước nguyên tố khác nhau
Phần tiêu đề “Bài 9. Số ước nguyên tố khác nhau”Nhập số nguyên dương n (n ≤ 1012). In ra số lượng ước nguyên tố khác nhau của n.
Ví dụ: nhập 360 thì in ra 3.
Kiểm tra: nhập 1001000.
Bài 10. Đếm ước bằng phân tích thừa số
Phần tiêu đề “Bài 10. Đếm ước bằng phân tích thừa số”Nhập số nguyên dương n (n ≤ 1012). In ra số ước của n, dùng phân tích thừa số nguyên tố.
Ví dụ: nhập 360 thì in ra 24.
Kiểm tra: nhập 735134400.
Bài 11. Số nửa nguyên tố
Phần tiêu đề “Bài 11. Số nửa nguyên tố”Số nửa nguyên tố là số bằng tích của hai số nguyên tố (có thể bằng nhau), ví dụ 6 = 2 × 3, 9 = 3 × 3. Nhập số nguyên dương n (n ≤ 1012), in ra YES nếu n là số nửa nguyên tố, ngược lại in ra NO.
Ví dụ: nhập 91 thì in ra YES.
Kiểm tra: nhập 999962000357.
Nhóm 3. Các bài toán quen thuộc
Phần tiêu đề “Nhóm 3. Các bài toán quen thuộc”Bài 12. Số có đúng ba ước
Phần tiêu đề “Bài 12. Số có đúng ba ước”Nhập số nguyên dương n (n ≤ 1010). Đếm xem từ 1 đến n có bao nhiêu số có đúng ba ước.
Ví dụ: nhập 50 thì in ra 4.
Kiểm tra: nhập 100000000.
Bài 13. Cặp số nguyên tố sinh đôi
Phần tiêu đề “Bài 13. Cặp số nguyên tố sinh đôi”Hai số nguyên tố hơn kém nhau 2 đơn vị gọi là cặp số nguyên tố sinh đôi, ví dụ (3, 5), (11, 13). Nhập số nguyên dương n (n ≤ 105), đếm số cặp sinh đôi mà cả hai số đều không vượt quá n.
Ví dụ: nhập 20 thì in ra 4.
Kiểm tra: nhập 1000.
Bài 14. Giả thuyết Goldbach
Phần tiêu đề “Bài 14. Giả thuyết Goldbach”Giả thuyết Goldbach nói rằng mọi số chẵn lớn hơn 2 đều viết được thành tổng hai số nguyên tố. Nhập số chẵn n (4 ≤ n ≤ 109), in ra hai số nguyên tố p ≤ q có p + q = n, với p nhỏ nhất có thể.
Ví dụ: nhập 28 thì in ra 5 23.
Kiểm tra: nhập 1000.
Bài 15. Số cách viết Goldbach
Phần tiêu đề “Bài 15. Số cách viết Goldbach”Nhập số chẵn n (4 ≤ n ≤ 105). Đếm số cặp số nguyên tố (p, q) với p ≤ q và p + q = n.
Ví dụ: nhập 10 thì in ra 2.
Kiểm tra: nhập 100.
Bài 16. Số nguyên tố đối xứng
Phần tiêu đề “Bài 16. Số nguyên tố đối xứng”Nhập số nguyên dương n (n ≤ 105). Đếm các số không vượt quá n vừa là số nguyên tố, vừa là số đối xứng (đọc xuôi ngược như nhau, ví dụ 131).
Ví dụ: nhập 100 thì in ra 5.
Kiểm tra: nhập 1000.
Bài 17. Số siêu nguyên tố
Phần tiêu đề “Bài 17. Số siêu nguyên tố”Số siêu nguyên tố là số nguyên tố mà khi bỏ dần các chữ số bên phải, các số còn lại vẫn là số nguyên tố. Ví dụ 2333 là số siêu nguyên tố vì 2333, 233, 23, 2 đều là số nguyên tố. Nhập k (1 ≤ k ≤ 8), in ra số lượng số siêu nguyên tố có đúng k chữ số.
Ví dụ: nhập 2 thì in ra 9.
Kiểm tra: nhập 4.
Bài 18. Số nguyên tố thứ k
Phần tiêu đề “Bài 18. Số nguyên tố thứ k”Nhập số nguyên dương k (k ≤ 104). In ra số nguyên tố thứ k (số nguyên tố thứ nhất là 2).
Ví dụ: nhập 5 thì in ra 11.
Kiểm tra: nhập 1000.
Bài 19. Khoảng trống lớn nhất
Phần tiêu đề “Bài 19. Khoảng trống lớn nhất”Nhập số nguyên dương n (3 ≤ n ≤ 105). Trong các cặp số nguyên tố liên tiếp p, q không vượt quá n, tìm cặp có hiệu q - p lớn nhất. In ra p và q; nếu có nhiều cặp thì in cặp có p nhỏ nhất.
Ví dụ: nhập 30 thì in ra 23 29.
Kiểm tra: nhập 1000.
Nhóm 4. Số nguyên tố trong giai thừa
Phần tiêu đề “Nhóm 4. Số nguyên tố trong giai thừa”Bài 20. Chữ số 0 tận cùng của n!
Phần tiêu đề “Bài 20. Chữ số 0 tận cùng của n!”Nhập số nguyên dương n (n ≤ 1018). In ra số chữ số 0 tận cùng của n! = 1 × 2 × … × n.
Ví dụ: nhập 100 thì in ra 24.
Kiểm tra: nhập 1000.
Bài 21. Số mũ của p trong n!
Phần tiêu đề “Bài 21. Số mũ của p trong n!”Nhập số nguyên dương n (n ≤ 1018) và số nguyên tố p (p ≤ 109). In ra số mũ lớn nhất k sao cho n! chia hết cho pk.
Ví dụ: nhập 10 2 thì in ra 8.
Kiểm tra: nhập 100 3.
© 2026 Bumbii Academy. Toàn bộ nội dung thuộc bản quyền của Bumbii Academy, nghiêm cấm sao chép dưới mọi hình thức khi chưa được cho phép.