หาตัวหารร่วม (Common Divisors) ของสองจำนวนใน Python

โจทย์: กำหนดสองจำนวนเต็ม หาตัวหารร่วมทั้งหมด

อัลกอริทึม

1. หาค่า min(a, b)
2. ตรวจสอบหารได้จาก 1 ถึง min
3. นับ/เก็บตัวที่หารทั้งคู่ลงตัว

ตัวอย่างโค้ด Python

a = 5
b = 45

count = 0
common_divisors = []

for i in range(1, min(a, b) + 1):
    if a % i == 0 and b % i == 0:
        count += 1
        common_divisors.append(i)

print("Count:", count)
print("Common divisors:", common_divisors)
# Output: Count: 2, Common divisors: [1, 5]

ผลลัพธ์

2

วิธีที่ดีกว่า: ใช้ GCD

import math

def common_divisors(a, b):
    g = math.gcd(a, b)
    divisors = []
    for i in range(1, int(math.sqrt(g)) + 1):
        if g % i == 0:
            divisors.append(i)
            if i != g // i:
                divisors.append(g // i)
    return sorted(divisors)

print(common_divisors(5, 45))  # [1, 5]
print(common_divisors(12, 18)) # [1, 2, 3, 6]

ความซับซ้อน: วิธี naive O(min(a,b)), วิธี GCD O(√gcd) - เร็วกว่ามากเมื่อตัวเลขใหญ่