Greatest Common Divisor (GCD) dan Least Common Multiple (LCM) plus Source Code VB.Net dan CSharp

Greatest Common Divisor (GCD) / Faktor Persekutuan Terbesar (FPB)

Kita mengetahui bahwa faktor-faktor 30 adalah 1, 2, 3, 5, 6, 10, 15, dan 30. Serta faktor-faktor persekutuan dari 105 adalah 1, 3, 5, 7, 15, 21, 35, dan 105. Maka dapat disimpulkan bahwa 1, 3, 5, dan 15 adalah faktor-faktor persekutuan (pembagi-pembagi bersama/common divisor) dari 30 dan 105. Sedangkan 15 merupakan Greatest Common Divisor (GCD) / Faktor Persekutuan Terbesar (FPB) dari 30 dan 15 (atau bisa ditulis gcd(30,105) = 15).

Tetapi bagaimana mencari gcd dari bilangan-bilangan yang besar. Seperti gcd(4840,1512). Maka diperlukan suatu alogaritma untuk dapat menyelesaikannya dengan lebih cepat. Salah satu alogaritma tersebut adalah alogaritma pembagian.

Alogaritma Pembagian

Diberikan dua bilangan bulat a dan b dengan a,b > 0 maka ada tepat satu pasangan bilangan-bilangan q dan r sehingga

b = qa + r dengan 0 ≤ r < a

GCD atau FPB dapat dicari dengan mengulang alogaritma pembagian

a = q1b + r1	0 < r1 < b
b = q2r1 + r2	0 < r2 < r1
r1 = q3r2 + r3	0 < r3 < r2
…	…
rn-2 = qnrn-1 + rn	0 < rn < rn-1
rn-1 = qn+1rn + rn	0 < r1 < b

maka r_n sisa pembagian di atas yang bukan 0 adalah gcd(a,b)

Contoh:
Tentukan gcd(4840,1512)!

4840 = 3 × 1512 + 304
1512 = 4 × 304 + 296
304 = 1 × 296 + 8 
296 = 37 × 8 + 0

maka gcd(4840,1512) = 8

Least Common Multiple (LCM) / Kelipatan Persekutuan Terkecil (KPK)

Jika A adalah himpunan kelipatan positif dari 5, yaitu A = {5, 10, 15, …} dan B adalah kelipatan positif dari 3, yaitu B = {3, 6, 9, …}, maka irisan A dan B, yaitu A ∩ B = {15, 30, 45, …} adalah himpunan kelipatan persekutuan (common multiple) dari 5 dan 3. Sedangkan 15 adalah Least Common Multiple (LCM) / Kelipatan Persekutuan Terkecil (KPK) dari 3 dan 5 (lcm(3,5) = 15).

LCM atau KPK dari dua bilangan a dan b dapat dicari dengan
lcm(a,b) = ab / gcd(a,b)

 

Source Code

VB.NET (VB 2005, VB 2008, VB 2010)

''' <summary>
''' Greates Common Divisor (GCD) from two numbers
''' </summary>
''' <param name="x">Number must be possitive integer</param>
''' <param name="y">Number must be possitive integer</param>
''' <returns>GCD from a and b</returns>
''' <remarks></remarks>
Public Function Gcd(ByVal x As Integer, ByVal y As Integer) As Integer
    Dim a, b, r As Integer

    If x < y Then
        a = System.Math.Abs(x)
        b = System.Math.Abs(y)
    Else
        b = System.Math.Abs(x)
        a = System.Math.Abs(y)
    End If

    Do
        r = a Mod b
        If r = 0 Then Exit Do
        a = b
        b = r
    Loop

    Return b
End Function

''' <summary>
''' Least Common Multiple (LCM) from two numbers
''' </summary>
''' <param name="x">Number must be possitive integer</param>
''' <param name="y">Number must be possitive integer</param>
''' <returns>LCM from a and b</returns>
''' <remarks></remarks>

Public Function Lcm(ByVal x As Integer, ByVal y As Integer) As Integer
    Return (x * y) / Gcd(x, y)
End Function

CSharp (C#) (C# 2005, 2008, 2010)

/// <summary>
/// Greates Common Divisor (GCD) from two numbers
/// </summary>
/// <param name="x">Number must be possitive integer</param>
/// <param name="y">Number must be possitive integer</param>
/// <returns>GCD from a and b</returns>
/// <remarks></remarks>
public int Gcd(int x, int y)
{
    int a = 0;
    int b = 0;
    int r = 0;

    if (x < y) {
        a = System.Math.Abs(x);
        b = System.Math.Abs(y);
    } else {
        b = System.Math.Abs(x);
        a = System.Math.Abs(y);
    }

    do {
        r = a % b;
        if (r == 0)
            break; // TODO: might not be correct. Was : Exit Do
        a = b;
        b = r;
    } while (true);

    return b;
}

/// <summary>
/// Least Common Multiple (LCM) from two numbers
/// </summary>
/// <param name="x">Number must be possitive integer</param>
/// <param name="y">Number must be possitive integer</param>
/// <returns>LCM from a and b</returns>
/// <remarks></remarks>
public int Lcm(int x, int y)
{
    return (x * y) / Gcd(x, y);
}