ห.ร.ม. หรือ GCD (Greatest Common Divisor) ของเลขจำนวนเต็มสองตัวขึ้นไปคือจำนวนขนาดใหญ่ที่สุดที่หารเลขเหล่านั้นลงตัว
ค.ร.น. หรือ LCM (Least Common Multiple) ของเลขจำนวนเต็มสองตัวขึ้นไปคือจำนวนขนาดเล็กที่สุดที่หารด้วยเลขเหล่านั้นลงตัว
เราเขียนห.ร.ม.ของเลข $a$, $b$ ว่า $gcd(a,b)$ และ ค.ร.น.ของเลข $a$, $b$ ว่า $lcm(a, b)$
มีความสัมพันธ์อยู่ว่า $lcm(a,b) = \frac{|a b|}{gcd(a,b)}$ ดังนั้นถ้าเรารู้ $gcd$ เราก็จะรู้ $lcm$ หรือในทางกลับกันถ้ารู้ $lcm$ ก็จะรู้ $gcd$
สำหรับคนที่ไม่เข้าใจเครื่องหมาย $|...|$, $|x|$ เรียกว่าค่าสัมบูรณ์ของ $x$ คือระยะห่างจาก 0 ถึง $x$ จึงเป็นลบไม่ได้ ในภาษาไพธอนคำนวณได้ด้วย $abs(x)$
วิธีคำนวณ $gcd$ และ $lcm$ มีหลายแบบ ที่สอนกันในระดับมัธยมคือใช้วิธีแยกตัวประกอบเฉพาะ และวิธีของยูคลิด
ถ้าจะหา $gcd(a,b)$ เราก็ดูว่า $a$ มีตัวประกอบเฉพาะอะไรบ้างกี่ตัว $b$ มีตัวประกอบเฉพาะอะไรบ้างกี่ตัว แล้วคูณตัวประกอบที่ซ้ำกันจาก $a$ และ $b$ ก็จะได้ $gcd(a,b)$ (และรู้ $lcm(a, b)$ ด้วยเพราะ $lcm(a,b) = \frac{|a b|}{gcd(a,b)}$)
เราใช้ฟังก์ชั่น $ตัวประกอบเฉพาะ()$ ที่เคยคุยกันไปแล้วมาหาตัวประกอบเฉพาะได้ แล้วเทียบว่ามีตัวไหนที่ซ้ำกันบ้าง
import collections
def ตัวประกอบเฉพาะ(n):
"""
หาตัวประกอบที่เป็นจำนวนเฉพาะของจำนวนเต็มบวก n
ถ้าเอาผลที่ได้คูณกันจะได้ค่า n
เช่น ตัวประกอบเฉพาะ(12) คือ [2, 2, 3]
"""
if n < 0:
return [] #ไม่คำนวณจำนวนลบ
if n == 1:
return [1] #ตัวประกอบของ 1 คือ 1
factors = [] #ลิสต์ที่จะเก็บตัวประกอบต่างๆ
i = 2 #เริ่มโดยลองเอา i = 2 มาหาร n ดู
while i*i <= n: #เราจะหารไม่เกิน sqrt(n)
while n%i == 0: #ถ้าหารลงตัว เก็บตัวหารไว้ในคำตอบ ลดขนาด n ลงเป็นผลลัพธ์ของการหาร
factors.append(i)
n = n//i
i = i+1 #เมื่อ i หารลงตัวต่อไม่ได้แล้วให้ลอง i ตัวต่อไปมาหารดู
if n > 1: #ถ้าตัวหารที่ควรทดลองลองหมดแล้วแล้วผลลัพธ์จากการหารยังไม่ใช่ 1 แสดงว่ามันก็เป็นตัวประกอบเฉพาะด้วย
factors.append(n)
return factors #ส่งลิสต์ที่มีตัวประกอบที่หาได้ออกมาเป็นคำตอบ
def gcd_แบบตัวประกอบ(a,b):
"""
หาห.ร.ม.ของ a และ b
โดยวิธีแยกตัวประกอบของ a และ b
"""
fa = collections.Counter(ตัวประกอบเฉพาะ(a)) #ใช้ collections.Counter นับว่าตัวประกอบแต่ละตัวซ้ำกี่ครั้ง
fb = collections.Counter(ตัวประกอบเฉพาะ(b))
common_f = [] #ลิสต์สำหรับเก็บตัวประกอบที่จะเป็นห.ร.ม.
for factor in fa.keys(): #สำหรับตัวประกอบที่มีอยู่ในทั้ง a และ b ...
if factor in fb:
power = min(fa[factor], fb[factor]) #...ให้ดูว่าในอันไหนซ้ำน้อยกว่ากัน...
for i in range(power): #...แล้วไปเก็บในลิสต์ของตัวประกอบสำหรับห.ร.ม.
common_f.append(factor)
gcd = 1
for f in common_f: #ห.ร.ม.คือผลคูณของตัวประกอบที่เก็บไว้ในลิสต์
gcd = gcd * f
return gcd
def lcm_แบบตัวประกอบ(a,b):
"""
หาค.ร.น.ของ a และ b
โดยวิธีแยกตัวประกอบของ a และ b
"""
return abs(a*b)//gcd_แบบตัวประกอบ(a,b)
gcd_แบบตัวประกอบ(24, 36)
12
lcm_แบบตัวประกอบ(24, 36)
72
วิธีของยูคลิดเป็นวิธีหา $gcd$ และ $lcm$ ที่เร็วกว่าวิธีแยกตัวประกอบมากเมื่อ $a$ และ $b$ มีขนาดใหญ่มากๆวิธีหนึ่ง
ยูคลิดบันทึกวิธีนี้ไว้เมื่อสองพันกว่าปีมาแล้ว
ให้สังเกตว่าถ้า $gcd(a,b)$ หารทั้ง $a$ และ $b$ ลงตัว มันต้องหาร $a-b$ และ $b-a$ ลงตัวด้วย
ดังนั้นสมมุติว่า $a > b$ เราก็สามารถทำให้ขนาดปัญหาเล็กลงโดยเอา $b$ ไปลบออกจาก $a$ เรื่อยๆจน $b$ มีขนาดใหญ่กว่า แล้วเราก็สลับเอา $a$ ไปลบออกจาก $b$ เรื่อยๆบ้าง ทำอย่างนี้สลับไปมาจนกระทั่ง $a$ และ $b$ มีขนาดเท่ากันซึ่งเท่ากับ $gcd(a,b)$ นั่นเอง
ยกตัวอย่างเช่นถ้า $a = 42, b = 12$ แล้ว $gcd(a,b)$ คืออะไร
เราก็ทำการแทนที่ $gcd(a,b) = gcd(42, 12)$ ด้วย $gcd(42-12, 12) = gcd(30, 12)$
ตอนนี้ $a$ ยังมากกว่า $b$ อยู่ จึงลบ $b$ ออกจาก $a$ อีก กลายเป็น $gcd(30-12, 12) = gcd(18, 12)$
ตอนนี้ $a$ ยังมากกว่า $b$ อยู่ จึงลบ $b$ ออกจาก $a$ อีก กลายเป็น $gcd(18-12, 12) = gcd(6, 12)$
ตอนนี้ $b$ มากกว่า $a$ แล้ว จึงลบ $a$ ออกจาก $b$ กลายเป็น $gcd(6, 12-6) = gcd(6, 6)$
ตอนนี้ $a$ และ $b$ มีค่าเท่ากันแล้ว คำตอบ $gcd(42, 12)$ ก็มีค่าเท่ากับ $gcd(6,6) = 6$ นั่นเอง
เราสามารถเขียนเป็นฟังก์ชั่นในไพธอนช่วยเราคำนวณได้ดังนี้:
def gcd_ยูคลิด_ลบ(a,b):
"""
หาห.ร.ม.ของ a และ b
โดยวิธีลบซ้ำๆของยูคลิด
"""
while a != b: #ขณะที่ a ยังไม่เท่ากับ b ให้ลบซ้ำๆดังนี้
while a > b: #ถ้า a ยังมากกว่า b ให้ลบ b ออกจาก a
a = a - b
while b > a: #ถ้า b ยังมากกว่า a ให้ลบ a ออกจาก b
b = b - a
return a
def lcm_ยูคลิด_ลบ(a,b):
"""
หาค.ร.น.ของ a และ b
โดยวิธีลบซ้ำๆของยูคลิด
"""
return abs(a*b)//gcd_ยูคลิด_ลบ(a,b)
gcd_ยูคลิด_ลบ(42,12)
6
gcd_ยูคลิด_ลบ(24, 3339911)
1
gcd_ยูคลิด_ลบ(72, 120)
24
lcm_ยูคลิด_ลบ(72, 120)
360
เมื่อพิจารณาดูแล้ว การลบซ้ำๆในวิธีของยูคลิดนั้นเทียบเท่ากับการหาเศษจากการหารเลขทั้งสองตัวนั่นเอง เราจึงสามารถเขียนฟังก์ชั่นแบบใช้การหารแทนการลบได้ดังนี้:
def gcd_ยูคลิด_หาร(a,b):
"""
หาห.ร.ม.ของ a และ b
โดยหารแล้วดูเศษแบบยูคลิด
"""
if b == 0:
return a #gcd(a,0) = a
while b != 0: #ขณะที่ b ยังไม่เป็น 0 เราแทนที่ a, b ด้วย b, a%b (เศษจากการหาร a ด้วย b)
a, b = b, a%b
return(a)
def lcm_ยูคลิด_หาร(a,b):
"""
หาค.ร.น.ของ a และ b
โดยหารแล้วดูเศษแบบยูคลิด
"""
return abs(a*b)//gcd_ยูคลิด_หาร(a,b)
gcd_ยูคลิด_หาร(24, 144)
24
lcm_ยูคลิด_หาร(24, 144)
144
เมื่อขนาดของ $a$ และ $b$ ต่างกันมากๆ วิธีหารจะเร็วกว่าวิธีลบซ้ำๆได้หลายเท่า เช่นตัวอย่างข้างล่างต่างกันเป็นร้อยเท่า (แม้ว่าทั้งสองวิธีจะเร็วมากแล้วก็ตาม)
%time print(gcd_ยูคลิด_ลบ(12, 12_000_000))
12 CPU times: user 49.8 ms, sys: 1.2 ms, total: 51 ms Wall time: 50.1 ms
%time print(gcd_ยูคลิด_หาร(12, 12_000_000))
12 CPU times: user 92 µs, sys: 39 µs, total: 131 µs Wall time: 109 µs
เวลาเราเขียนฟังก์ชั่นหลายๆแบบที่ควรให้คำตอบเท่าๆกันเราอาจจะอยากตรวจสอบว่ามันให้คำตอบเท่ากันจริงหรือไม่โดยป้อนค่าสุ่มๆให้มันคำนวณหลายๆค่าดูแบบนี้ก็ได้ครับ:
#ทดสอบดูว่า gcd ที่เราหาด้วยวิธีต่างๆกันได้คำตอบเท่ากัน
#ถ้าไม่พบสิ่งผิดปกติจะไม่พิมพ์อะไรออกมา
import random
trials = 10_000
max_num = 1_000_000
for i in range(trials):
a = random.randint(1, max_num)
b = random.randint(1, max_num)
GCDs = [gcd_แบบตัวประกอบ(a,b), gcd_ยูคลิด_ลบ(a,b), gcd_ยูคลิด_หาร(a,b)]
if not all([x==GCDs[0] for x in GCDs]):
print(f"พบสิ่งผิดปกติ: {a}, {b}, {GCDs} ")