Số nguyên tố
Số nguyên tố là chủ đề xuất hiện nhiều 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 nên có nhiều hơn hai ước - không thỏa điều kiện số nguyên tố.
- 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. Có nhiều cách thử, cách sau thử ít số hơn cách trước.
Cách 1. Thử hết từ 2 đến n - 1
Phần tiêu đề “Cách 1. Thử hết từ 2 đến n - 1”Cách này đúng nhưng phải thử tất cả các số từ 2 đến n - 1 (vét cạn). Với n = 97 phải thử 95 số.
def la_nguyen_to(n): if n < 2: return False # 0 và 1 không phải số nguyên tố for d in range(2, n): # thử d = 2, 3, ..., n - 1 if n % d == 0: return False # tìm được ước, là hợp số 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 < n; d++) { // thử d = 2, 3, ..., n - 1 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;}Cách 2. Chỉ thử đến n/2
Phần tiêu đề “Cách 2. Chỉ thử đến n/2”Quan sát: ước lớn nhất của n (không kể chính n) không vượt quá . Xem vài ví dụ:
| n | Các ước của n | Ước lớn nhất (không kể n) | |
|---|---|---|---|
| 12 | 1, 2, 3, 4, 6, 12 | 6 | 6 |
| 15 | 1, 3, 5, 15 | 5 | 7,5 |
| 20 | 1, 2, 4, 5, 10, 20 | 10 | 10 |
| 21 | 1, 3, 7, 21 | 7 | 10,5 |
Từ quan sát trên, sẽ không có ước nào lớn hơn nên chỉ cần thử từ 2 đến . Với cách này, số phép kiểm tra giảm đi một nửa: với n = 97 chỉ còn thử 47 số (2 đến 48) thay vì 95.
def la_nguyen_to(n): if n < 2: return False # 0 và 1 không phải số nguyên tố for d in range(2, n // 2 + 1): # thử d = 2, 3, ..., n // 2 if n % d == 0: return False # tìm được ước, là hợp số 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 <= n / 2; d++) { // thử d = 2, 3, ..., n / 2 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;}Cách 3. Chỉ thử đến
Phần tiêu đề “Cách 3. Chỉ thử đến n\sqrt{n}n”Theo bài Ước và bội, nếu n = a × b với a ≤ b thì a ≤ . 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á . Chỉ cần thử d từ 2 đến .
Ví dụ n = 36 ( = 6). Các cặp ước của 36:
| Cặp ước | Số nhỏ | Số lớn |
|---|---|---|
| 1 × 36 | 1 | 36 |
| 2 × 18 | 2 | 18 |
| 3 × 12 | 3 | 12 |
| 4 × 9 | 4 | 9 |
| 6 × 6 | 6 | 6 |
Số nhỏ trong mỗi cặp luôn ≤ 6, số lớn luôn ≥ 6. Nên nếu thử hết d từ 2 đến 6 mà không gặp ước nào thì phía trên 6 cũng không có ước nào (trừ chính n).
Chạy tay với n = 97 ( ≈ 9,8):
| d | d × d | 97 chia hết cho d? |
|---|---|---|
| 2 | 4 | không |
| 3 | 9 | không |
| 4 | 16 | không |
| 5 | 25 | không |
| 6 | 36 | không |
| 7 | 49 | không |
| 8 | 64 | không |
| 9 | 81 | không |
| 10 | 100 > 97 | dừng |
Không có ước nào nên 97 là số nguyên tố, chỉ mất 8 lần thử. Với n = 91 thì thử 2, 3, 4, 5, 6 không chia hết, đến d = 7 thì 91 = 7 × 13, dừng ngay: 91 là hợp số.
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;}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ố.
Cách 4. Chỉ thử các số lẻ đến
Phần tiêu đề “Cách 4. Chỉ thử các số lẻ đến n\sqrt{n}n”Trừ số 2, tất cả các số nguyên tố khác đều lẻ (mọi số chẵn khác đều chia hết cho 2). Nên:
- n = 2 là số nguyên tố; n chẵn lớn hơn 2 là hợp số, kết luận ngay.
- n lẻ thì không chia hết cho số chẵn nào, chỉ cần thử các số lẻ 3, 5, 7, … không vượt quá .
Với n = 97: thử 2, rồi 3, 5, 7, 9, tức 5 số.
def la_nguyen_to(n): if n < 2: return False # 0 và 1 không phải số nguyên tố if n == 2: return True if n % 2 == 0: return False # số chẵn lớn hơn 2 là hợp số d = 3 while d * d <= n: if n % d == 0: return False # tìm được ước, là hợp số d += 2 # chỉ thử số lẻ 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ố if (n == 2) return true; if (n % 2 == 0) return false; // số chẵn lớn hơn 2 là hợp số for (long long d = 3; d * d <= n; d += 2) { // chỉ thử số lẻ 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;}So sánh các cách
Phần tiêu đề “So sánh các cách”Số lần thử nhiều nhất (khi n là số nguyên tố):
| Cách | Thử d | n = 97 | n là số nguyên tố gần 1012 |
|---|---|---|---|
| 1 | 2 đến n - 1 | 95 | ≈ 1012 |
| 2 | 2 đến | 47 | ≈ 5 × 1011 |
| 3 | 2 đến | 8 | 106 |
| 4 | 2, rồi số lẻ đến | 5 | 5 × 105 |
Với n là số nguyên tố gần 1012: cách 2 bớt được một nửa số lần thử so với cách 1. Cách 3 chỉ thử khoảng 106 số, ít hơn cách 1 khoảng 106 lần (một triệu lần). Cách 4 bớt thêm một nửa so với cách 3, còn khoảng 5 × 105 lần thử.
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 = 16 > 5 nên dừng, không thử nữa | 5 |
Dòng d = 4 chỉ là lúc vòng lặp dừng: giống Cách 3 ở phần kiểm tra số nguyên tố, chỉ cần thử d khi d × d ≤ n. 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 thử cả 4, 6, 8… dù chúng không phải số nguyên tố? Muốn chỉ thử số nguyên tố thì phải biết trước d có nguyên tố không, tốn thêm công. Thử hết d = 2, 3, 4, … lại không sai: lúc tới d = 4, mọi thừa số 2 đã bị chia hết ra rồi, nên n không còn chia hết cho 4 (hay 6, 8…). Vậy mỗi khi n chia hết cho d thì d chắc chắn là số nguyên tố.
n = int(input())goc = n # giữ lại n ban đầu để incac_thua_so = [] # ví dụ ["2^3", "3^2", "5"]d = 2while d * d <= n: so_mu = 0 while n % d == 0: n //= d so_mu += 1 if so_mu == 1: cac_thua_so.append(str(d)) elif so_mu > 1: cac_thua_so.append(str(d) + "^" + str(so_mu)) d += 1if n > 1: cac_thua_so.append(str(n)) # phần còn lại là một số nguyên tốprint(goc, "=", " * ".join(cac_thua_so)) # 360 = 2^3 * 3^2 * 5#include <iostream>#include <string>using namespace std;
int main() { long long n; cin >> n; cout << n << " ="; string dau = " "; // trước thừa số đầu là " ", sau đó là " * " for (long long d = 2; d * d <= n; d++) { int soMu = 0; while (n % d == 0) { n /= d; soMu++; } if (soMu > 0) { cout << dau << d; if (soMu > 1) cout << "^" << soMu; dau = " * "; } } if (n > 1) cout << dau << n; // phần còn lại là một số nguyên tố cout << endl; // 360 = 2^3 * 3^2 * 5 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.
Quy tắc chung: cộng 1 vào mỗi số mũ rồi nhân lại. Trong ví dụ 360, số ước = (3 + 1) × (2 + 1) × (1 + 1) = 4 × 3 × 2 = 24.
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, nên mỗi chữ số 0 cần một số 2 và một số 5 trong tích.
Số 2 không chỉ nằm ở thừa số “2” của tích: các số 4, 6, 8… cũng chứa số 2 khi phân tích ra thừa số nguyên tố (như phần Phân tích thừa số nguyên tố ở trên). Ví dụ với 10! = 1 × 2 × 3 × … × 10, phân tích từng số rồi đếm xem có bao nhiêu số 2, bao nhiêu số 5:
| Số | Phân tích | Số lượng số 2 | Số lượng số 5 |
|---|---|---|---|
| 2 | 2 | 1 | 0 |
| 4 | 2 × 2 | 2 | 0 |
| 5 | 5 | 0 | 1 |
| 6 | 2 × 3 | 1 | 0 |
| 8 | 2 × 2 × 2 | 3 | 0 |
| 10 | 2 × 5 | 1 | 1 |
| Cộng | 8 | 2 |
(Các số 1, 3, 7, 9 không chứa số 2 hay số 5 nào.) Vậy 10! có 8 số 2 và 2 số 5. Ghép được 2 cặp 2 × 5 = 10, nên 10! = 3628800 có 2 chữ số 0 tận cùng. 6 số 2 còn lại không có số 5 để ghép nên không tạo thêm chữ số 0.
Số 2 luôn nhiều hơn số 5 vì cứ 2 số liền nhau lại có một số chẵn (chứa ít nhất một số 2), còn phải 5 số liền nhau mới có một số chia hết cho 5. Đếm tương tự cho 100! thì được 97 số 2 nhưng chỉ có 24 số 5. Vì số 5 luôn ít hơn, mỗi số 5 đều có một số 2 để ghép, nên số chữ số 0 tận cùng bằng số lượng số 5 khi phân tích n! ra thừa số nguyên tố.
Đếm số 5 trong 100!:
- Các số chia hết cho 5 (5, 10, …, 100), mỗi số chứa ít nhất một số 5: 100 // 5 = 20.
- Các số chia hết cho 25 (25, 50, 75, 100) chứa hai số 5 (vì 25 = 5 × 5), dòng trên mới đếm một, nên đếm thêm một lần 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 26 bài, chia thành 5 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. Vận dụng phân tích thừa số
Phần tiêu đề “Nhóm 4. Vận dụng phân tích thừa số”Bài 20. Số chỉ có ước nguyên tố 2, 3, 5
Phần tiêu đề “Bài 20. Số chỉ có ước nguyên tố 2, 3, 5”Nhập số nguyên dương n (n ≤ 1018). In ra YES nếu n không có ước nguyên tố nào khác 2, 3 và 5 (số 1 cũng tính là YES), ngược lại in ra NO.
Ví dụ: nhập 60 thì in ra YES.
Kiểm tra: nhập 1215000000.
Bài 21. Số không có ước chính phương
Phần tiêu đề “Bài 21. Số không có ước chính phương”Nhập số nguyên dương n (n ≤ 1012). In ra YES nếu n không chia hết cho số chính phương nào lớn hơn 1 (4, 9, 16, 25, …), ngược lại in ra NO.
Ví dụ: nhập 30 thì in ra YES.
Kiểm tra: nhập 999966000289.
Bài 22. Nhân thêm để được số chính phương
Phần tiêu đề “Bài 22. Nhân thêm để được số chính phương”Nhập số nguyên dương n (n ≤ 1012). In ra số nguyên dương k nhỏ nhất sao cho n × k là số chính phương.
Ví dụ: nhập 12 thì in ra 3.
Kiểm tra: nhập 999999999999.
Nhóm 5. Số nguyên tố trong giai thừa
Phần tiêu đề “Nhóm 5. Số nguyên tố trong giai thừa”Bài 23. Chữ số 0 tận cùng của n!
Phần tiêu đề “Bài 23. 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 24. Số mũ của p trong n!
Phần tiêu đề “Bài 24. 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.
Bài 25. Số ước của n!
Phần tiêu đề “Bài 25. Số ước của n!”Nhập số nguyên dương n (n ≤ 105). In ra số ước của n! chia lấy dư cho 109 + 7.
Ví dụ: nhập 5 thì in ra 16.
Kiểm tra: nhập 100.
Bài 26. Giai thừa có ít nhất k chữ số 0
Phần tiêu đề “Bài 26. Giai thừa có ít nhất k chữ số 0”Nhập số nguyên dương k (k ≤ 1012). In ra số n nhỏ nhất sao cho n! có ít nhất k chữ số 0 tận cùng.
Ví dụ: nhập 6 thì in ra 25.
Kiểm tra: nhập 1000000.