Bab 10 · Matematika Terapan

Prima, FPB & KPK

Bilangan prima adalah "atom" dari semua bilangan bulat — setiap bilangan lain bisa dibongkar jadi kombinasi prima. Dari sinilah FPB dan KPK diturunkan.

KonsepBilangan prima

Bilangan prima hanya bisa dibagi rata oleh 1 dan dirinya sendiri. 1 bukan prima (kesepakatan matematika), dan 2 adalah prima genap satu-satunya.

Faktorisasi prima → FPB & KPK

Kode JRGAlgoritma Euclid untuk FPB

Membongkar ke faktor prima itu lambat untuk angka besar. Ada cara jauh lebih cepat berumur 2000+ tahun: algoritma Euclid — FPB(a,b) = FPB(b, a mod b), diulang sampai sisa baginya nol.

fn fpb(a: int, b: int) -> int {
    let mut x = a
    let mut y = b
    while y != 0 {
        let sisa = x % y
        x = y
        y = sisa
    }
    return x
}

fn kpk(a: int, b: int) -> int {
    return (a * b) / fpb(a, b)
}

pub fn main() {
    wok("FPB(18,30) =", fpb(18, 30))
    wok("KPK(18,30) =", kpk(18, 30))
}

FPB(18,30) = 6
KPK(18,30) = 90