Ví dụ tổng hợp - số nguyên tố và ước chung

Bài 6/6 · khoảng 8 phút đọc

Hãy kết hợp hàm (Chương 4) với vòng lặp (chương này) để viết hai hàm toán học quen thuộc.

Kiểm tra số nguyên tố

Số nguyên tố là số lớn hơn 1 chỉ chia hết cho 1 và chính nó.

Python
def la_nguyen_to(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i = i + 1
    return True
 
print(la_nguyen_to(7))
print(la_nguyen_to(12))
print(la_nguyen_to(97))

Ý tưởng: thử chia n cho 2, 3, 4, …; nếu tìm được số chia hết thì n không phải số nguyên tố. Chỉ cần thử đến khi i * i vượt quá n.

Ước chung lớn nhất (thuật toán Euclid)

Python
def ucln(a, b):
    while b != 0:
        a, b = b, a % b
    return a
 
print(ucln(48, 18))
print(ucln(17, 5))

Thuật toán nhiều ngàn năm tuổi này lặp lại: thay (a, b) bằng (b, a % b) cho đến khi b bằng 0; lúc đó a là ước chung lớn nhất.

Dùng hàm để chia bài toán

Python
def la_nguyen_to(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True
 
def liet_ke_nguyen_to(gioi_han):
    for n in range(2, gioi_han + 1):
        if la_nguyen_to(n):
            print(n, end=" ")
 
liet_ke_nguyen_to(30)

Ghi nhớ: chia bài toán thành các hàm nhỏ, mỗi hàm làm một việc rõ ràng rồi ghép lại.

Vì sao `la_nguyen_to(1)` trả về `False`?

Vì theo định nghĩa số nguyên tố phải lớn hơn 1.

← Vòng lặp lồng nhauChuỗi là dãy ký tự - chỉ số và độ dài →
Ví dụ tổng hợp - số nguyên tố và ước chung · Lý thuyết Python · PyKid