การนับตัวหารร่วม (Common Divisors) ของสองจำนวน
หาจำนวนจำนวนเต็มบวกที่หาร a และ b ลงตัวทั้งคู่
อัลกอริทึม
- หา GCD ของ a และ b
- นับตัวหารของ GCD (เพราะตัวหารร่วมของ a,b คือตัวหารของ gcd(a,b))
ตัวอย่างโค้ด
from math import gcd
def solve(a, b):
res = 0
for i in range(1, gcd(a, b) + 1):
if (a % i) == 0 and (b % i) == 0:
res += 1
return res
a, b = 288, 240
print(solve(a, b))
ผลลัพธ์
10
ตัวหารร่วม
[1, 2, 3, 4, 6, 8, 12, 16, 24, 48] → 10 ตัว
การปรับปรุงประสิทธิภาพ
def solve_fast(a, b):
g = gcd(a, b)
count = 0
for i in range(1, int(g**0.5) + 1):
if g % i == 0:
count += 2 if i != g // i else 1
return count
