Dalam matematika, faktor persekutuan terbesar (FPB) dari dua bilangan asli adalah bilangan asli terbesar yang dapat membagi habis kedua bilangan tersebut. FPB memiliki banyak aplikasi dalam pemrograman dan matematika, seperti dalam mengurangi pecahan, menyederhanakan akar kuadrat, dan pemrosesan bilangan bulat.
Salah satu algoritma yang umum digunakan untuk mencari FPB dari dua bilangan adalah Algoritma Euclidean. Algoritma ini didasarkan pada sifat bahwa FPB dari dua bilangan sama dengan FPB dari bilangan yang tersisa setelah membagi bilangan pertama dengan bilangan kedua.
Terdapat sebuah soal:
Diberikan dua bilangan asli m dan n, cari faktor persekutuan terbesar dari kedua bilangan tersebut, yakni bilangan asli terbesar yang membagi habis kedua bilangan m dan n.
- Cari sisa bagi. Bagi m dengan n dan r sebagai sisa bagi (sehingga 0 r < n)
- Apakah 0? Jika r = 0, pencarian selesai, n adalah bilangan yang dicari
- Perkecil nilainya. Jadikan m ← n, n ← r, dan kembali ke langkah 1
Berikut ini adalah implementasi jawaban algoritma Euclidean menggunakan bahasa pemrograman Python:
def cari_fpb(m, n):
while n != 0:
r = m % n
m = n
n = r
return m
# Input bilangan m dan n
m = int(input("Masukkan bilangan m: "))
n = int(input("Masukkan bilangan n: "))
# Panggil fungsi cari_fpb dan cetak hasilnya
fpb = cari_fpb(m, n)
print("FPB dari", m, "dan", n, "adalah:", fpb)Dalam kode di atas, kita mendefinisikan fungsi `cari_fpb` yang mengambil dua parameter `m` dan `n`. Fungsi ini menggunakan algoritma Euclidean untuk mencari FPB dari kedua bilangan tersebut
Selanjutnya, kita mengambil input dari pengguna untuk bilangan `m` dan `n`. Kemudian, kita memanggil fungsi `cari_fpb` dengan parameter yang sesuai, dan hasilnya disimpan dalam variabel `fpb`. Akhirnya, kita mencetak hasilnya ke layar.
Sekarang, kita dapat menjalankan kode di atas dan mencoba beberapa contoh untuk mencari FPB dari dua bilangan asli:
Contoh 1:
Masukkan bilangan m: 12 Masukkan bilangan n: 8 FPB dari 12 dan 8 adalah: 4
Contoh 2:
Masukkan bilangan m: 24 Masukkan bilangan n: 36 FPB dari 24 dan 36 adalah: 12
Contoh 3:
Masukkan bilangan m: 17 Masukkan bilangan n: 23 FPB dari 17 dan 23 adalah: 1
Dengan menggunakan algoritma Euclidean, kita dapat dengan mudah mencari FPB dari dua bilangan asli menggunakan bahasa pemrograman Python. Algoritma ini efisien dan dapat diaplikasikan pada bilangan-bilangan yang lebih besar juga.