Bỏ qua để đến nội dung

Số nguyên tố

Mức độ: Cơ bản

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à 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.

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 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

Quan sát: ước lớn nhất của n (không kể chính n) không vượt quá n2\dfrac{n}{2}. Xem vài ví dụ:

nCác ước của nƯớc lớn nhất (không kể n)n2\dfrac{n}{2}
121, 2, 3, 4, 6, 1266
151, 3, 5, 1557,5
201, 2, 4, 5, 10, 201010
211, 3, 7, 21710,5

Từ quan sát trên, sẽ không có ước nào lớn hơn n2\dfrac{n}{2} nên chỉ cần thử từ 2 đến n2\dfrac{n}{2}. 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

Theo bài Ước và bội, nếu n = a × b với a ≤ b thì a ≤ n\sqrt{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\sqrt{n}. Chỉ cần thử d từ 2 đến n\sqrt{n}.

Ví dụ n = 36 (36\sqrt{36} = 6). Các cặp ước của 36:

Cặp ướcSố nhỏSố lớn
1 × 36136
2 × 18218
3 × 12312
4 × 949
6 × 666

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 (97\sqrt{97} ≈ 9,8):

dd × d97 chia hết cho d?
24không
39không
416không
525không
636không
749không
864không
981không
10100 > 97dừ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

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 n\sqrt{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á n\sqrt{n}.

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

Số lần thử nhiều nhất (khi n là số nguyên tố):

CáchThử dn = 97n là số nguyên tố gần 1012
12 đến n - 195≈ 1012
22 đến n2\dfrac{n}{2}47≈ 5 × 1011
32 đến n\sqrt{n}8106
42, rồi số lẻ đến n\sqrt{n}55 × 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ử.

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:

dChia liên tiếpSố lầnn còn lại
2360 → 180 → 90 → 45345
345 → 15 → 525
44 × 4 = 16 > 5 nên dừng, không thử nữa5

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 để in
cac_thua_so = [] # ví dụ ["2^3", "3^2", "5"]
d = 2
while 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 += 1
if 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

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ỗ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.

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íchSố lượng số 2Số lượng số 5
2210
42 × 220
5501
62 × 310
82 × 2 × 230
102 × 511
Cộng82

(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ố.

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ậ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.

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

1000003

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

999999999989

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

143

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

76127

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

2^3*5^3*7*11*13

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

3803

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

1344

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

1229

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

35

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

3 997

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

20

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

16

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

7919

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

887 907

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

111111111111

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

249

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

48

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

583951250

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

4000005

Hướng dẫn giải chi tiết: liên hệ tác giả.

Th.S Trần Huy Phúc

Th.S Trần Huy Phúc

Principal Software Engineer @Adnovum & Bumbii Academy