My first Magazine pemrograman-kompetitif-dasar | Page 22

2 Matematika Diskret Dasar
Anda perlu berhati-hati pada kasus pembagian, karena aritmetika modular tidak serta-merta
bekerja. Diketahui sifat berikut:
a
mod m 6 =
b 
12
mod 6 6 =
4 
a mod m
b mod m

mod m.
Contoh:
Pada aritmetika modular,
a
b
12 mod 6
4 mod 6

mod 6.
mod m biasa ditulis sebagai:
a × b −1


mod m
dengan b −1 adalah modular multiplicative inverse dari b. Perhitungan Modular multiplicative
inverse tidak dibahas pada buku ini. Namun, jika Anda penasaran, modular multiplicative inverse
dapat dihitung menggunakan algoritma extended euclid 5 atau memanfaatkan teorema Euler. 6
2.2
Bilangan Prima
Bilangan prima merupakan bilangan bulat positif yang tepat memiliki dua faktor (pembagi),
yaitu 1 dan dirinya sendiri. Beberapa contoh bilangan prima adalah 2, 3, 5, 13, 97.
Lawan dari bilangan prima adalah bilangan komposit. Bilangan komposit adalah bilangan
yang memiliki lebih dari dua faktor. Contoh dari bilangan komposit adalah 6, 14, 20, 25.
2.2.1
Uji Keprimaan (Primality Testing )
Aktivitas untuk mengecek apakah suatu bilangan bulat N adalah bilangan prima disebut
dengan uji keprimaan (primality testing ). Solusi yang mudah untuk mengecek apakah N meru-
pakan bilangan prima dapat dilakukan dengan mengecek apakah ada bilangan selain 1 dan N yang
habis membagi N. Kita dapat melakukan iterasi dari 2 hingga N − 1 untuk mengetahui apakah ada
bilangan selain 1 dan N yang habis membagi N. Kompleksitas waktu untuk solusi ini adalah O(N).
Solusi ini dapat dilihat pada Algoritma 3.
Algoritma 3 Uji keprimaan dengan melakukan pengecekan dari 2 sampai N-1.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12
function IS P RIME N AIVE (N)
if N ≤ 1 then
return f alse
end if
for i ← 2, N − 1 do
if N mod i = 0 then
return f alse
end if
end for
return true
end function