การหาห.ร.ม.และค.ร.น.

ห.ร.ม. หรือ 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)}$)

เราใช้ฟังก์ชั่น $ตัวประกอบเฉพาะ()$ ที่เคยคุยกันไปแล้วมาหาตัวประกอบเฉพาะได้ แล้วเทียบว่ามีตัวไหนที่ซ้ำกันบ้าง

In [1]:
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)
In [2]:
gcd_แบบตัวประกอบ(24, 36)
Out[2]:
12
In [3]:
lcm_แบบตัวประกอบ(24, 36)
Out[3]:
72

วิธีคำนวณด้วยวิธีของยูคลิด (Euclid's algorithm)

วิธีของยูคลิดเป็นวิธีหา $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$ นั่นเอง

เราสามารถเขียนเป็นฟังก์ชั่นในไพธอนช่วยเราคำนวณได้ดังนี้:

In [4]:
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)
In [5]:
gcd_ยูคลิด_ลบ(42,12)
Out[5]:
6
In [6]:
gcd_ยูคลิด_ลบ(24, 3339911)
Out[6]:
1
In [7]:
gcd_ยูคลิด_ลบ(72, 120)
Out[7]:
24
In [8]:
lcm_ยูคลิด_ลบ(72, 120)
Out[8]:
360

เมื่อพิจารณาดูแล้ว การลบซ้ำๆในวิธีของยูคลิดนั้นเทียบเท่ากับการหาเศษจากการหารเลขทั้งสองตัวนั่นเอง เราจึงสามารถเขียนฟังก์ชั่นแบบใช้การหารแทนการลบได้ดังนี้:

In [9]:
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)
In [10]:
gcd_ยูคลิด_หาร(24, 144)
Out[10]:
24
In [11]:
lcm_ยูคลิด_หาร(24, 144)
Out[11]:
144

เมื่อขนาดของ $a$ และ $b$ ต่างกันมากๆ วิธีหารจะเร็วกว่าวิธีลบซ้ำๆได้หลายเท่า เช่นตัวอย่างข้างล่างต่างกันเป็นร้อยเท่า (แม้ว่าทั้งสองวิธีจะเร็วมากแล้วก็ตาม)

In [12]:
%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
In [13]:
%time print(gcd_ยูคลิด_หาร(12, 12_000_000))
12
CPU times: user 92 µs, sys: 39 µs, total: 131 µs
Wall time: 109 µs

เวลาเราเขียนฟังก์ชั่นหลายๆแบบที่ควรให้คำตอบเท่าๆกันเราอาจจะอยากตรวจสอบว่ามันให้คำตอบเท่ากันจริงหรือไม่โดยป้อนค่าสุ่มๆให้มันคำนวณหลายๆค่าดูแบบนี้ก็ได้ครับ:

In [14]:
#ทดสอบดูว่า 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} ")