Greatest Common Divisor

วันนี้กลับไปอ่านหนังสือ discrete math สมัยเรียนมหาลัย ไปเจอบทนึงพูดถึงเรื่อง GCD หรือ Great Common Divisor หรือในไทยก็ ห.ร.ม. หรือ หารร่วมมาก

วิธีการหาหารร่วมมากโดยปรกติ ก็ คือ แยก factor ของตัวเลข 2 ตัวที่ต้องการหา GCD แล้วก็นำมาหารกันจนเหลือตัวที่ไม่สามารถหารกันลงแล้ว

เช่น

GCD(14, 56) = 2x7 and 2x2x2x7 = 1 and 2x7 = 14

วิธีเขียน Program ก็อาจจะทำได้โดย

int GCD(int a, int b)
{
    int temp = a;
    int temp2 = b;

    int gcd = 1;
    while((temp % 2 == 0) && (temp2 % 2 == 0))
    {
        temp /= 2;
        temp2 /= 2;
        gcd *= 2;
    }
    for(int i = 3; i <= a && i <= b; i+=2)
    {
        while((temp  % i == 0) && (temp2 % i == 0))
        {       
            temp /= i;
            temp2 /= i;
            gcd *= i;
        }       
    }
    return gcd;
}

แต่มีอีกหลายวิธีที่ทำได้รวดเร็วกว่าวิธีที่เสนอมานี้เยอะมาก วิธีนึงก็คือ วิธี Euclidean วิธีให้ความคิดไว้ว่า GCD ของ a กับ b เท่ากับ GCD ของ b กับ abs(a-b) หรือสามารถเขียนเป็น program ได้ดังนี้

int GCD(int a, int b)
{
   if(a % b == 0)
   {
       return b;
   }
   else   
   {
       return GCD(b, abs(a - b));
   }
}

จะเห็นได้ว่า วิธี Euclidean ทำให้ program ง่ายขึ้นและรวดเร็วขึ้นด้วย