Least Common Multiple Algorithm

LCM (Kelipatan Terkecil)

Pahami cara menghitung LCM dengan mudah!

Apa itu LCM?

LCM, atau Least Common Multiple, adalah kelipatan terkecil yang dapat dibagi oleh dua bilangan atau lebih tanpa sisa. Dengan kata lain, LCM adalah bilangan bulat positif terkecil yang merupakan kelipatan dari semua bilangan yang diberikan.

Cara Menemukan LCM

Terdapat beberapa metode untuk menghitung LCM, di antaranya:

1. Metode Faktorisasi Prima: Temukan faktorisasi prima dari setiap bilangan, lalu ambil setiap faktor dengan pangkat tertinggi yang muncul.
2. Metode Daftar Kelipatan: Daftarkan kelipatan dari masing-masing bilangan hingga menemukan kelipatan yang sama.
3. Menggunakan GCD: LCM dapat dihitung menggunakan rumus:
   LCM(a, b) = |a × b| / GCD(a, b),
   di mana GCD adalah Greatest Common Divisor atau Faktor Persekutuan Terbesar.

Contoh Perhitungan LCM

Mari kita hitung LCM dari 4 dan 5 dengan beberapa metode.

1. Metode Daftar Kelipatan:

Kelipatan dari 4: 4, 8, 12, 16, 20, 24, ...
Kelipatan dari 5: 5, 10, 15, 20, 25, ...
LCM dari 4 dan 5 adalah 20.

2. Metode Faktorisasi Prima:

Faktorisasi prima dari 4: 2²
Faktorisasi prima dari 5: 5¹
Ambil faktor dengan pangkat tertinggi: 2² × 5¹ = 20.

3. Menggunakan GCD:

Untuk menghitung LCM dengan efisien, kita dapat menggunakan rumus:
LCM(a, b) = |a × b| / GCD(a, b)

Contoh:

• LCM(4, 5): LCM adalah 4 × 5 / GCD(4, 5) = 20 / 1 = 20.
• LCM(12, 15): LCM adalah 12 × 15 / GCD(12, 15) = 180 / 3 = 60.
• LCM(7, 3): LCM adalah 7 × 3 / GCD(7, 3) = 21 / 1 = 21.

Kompleksitas Algoritma

1. Kompleksitas Waktu

Algoritma Euclid untuk menghitung GCD memiliki kompleksitas waktu O(log(min(a, b))), karena setiap langkah mengurangi nilai bilangan setidaknya setengah dari sebelumnya. Oleh karena itu, kompleksitas waktu untuk menghitung LCM adalah:

O(log(min(a, b)))

2. Kompleksitas Ruang

Kompleksitas ruang untuk algoritma ini adalah O(1) karena tidak menggunakan struktur data yang bergantung pada ukuran input. Semua operasi dilakukan dengan beberapa variabel lokal.

Contoh Kode

def gcd(a, b):
    while b:
        a, b = b, a % b
    return abs(a)

def lcm(a, b):
    return abs(a * b) // gcd(a, b)

# Contoh penggunaan
pairs = [(4, 5), (12, 15), (7, 3)]

for a, b in pairs:
    print(f"LCM dari {a} dan {b} adalah {lcm(a, b)}")

Kesimpulan

Menghitung LCM menggunakan GCD adalah metode yang efisien baik dalam hal waktu maupun ruang. Dengan memanfaatkan hubungan antara LCM dan GCD, kita dapat dengan mudah menghitung LCM untuk dua bilangan atau lebih. Metode ini sangat berguna dalam berbagai aplikasi matematika dan pemrograman.