My first Magazine pemrograman-kompetitif-dasar | Page 23

2.2 Bilangan Prima
Terdapat solusi uji keprimaan yang
√ lebih cepat
√ daripada O(N). Manfaatkan observasi bahwa
jika N = a × b, dan a ≤ b, maka a ≤ N dan b ≥ N. Kita tidak perlu memeriksa b; seandainya
√
N habis dibagi b, tentu N habis dibagi
a.
Jadi
kita
hanya
perlu
memeriksa
hingga
N. Jadi
√
kompleksitas waktunya adalah O( N). Solusi ini dapat dilihat pada Algoritma 4.
Algoritma 4 Uji keprimaan dengan melakukan pengecekan dari 2 sampai
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
function IS P RIME S QRT (N)
if N ≤ 1 then
return f alse
end if
i ← 2
while i × i ≤ N do
if N mod i = 0 then
return f alse
end if
i ← i + 1
end while
return true
end function
2.2.2
√
N.
. Pertidaksamaan ini ekuivalen dengan i ≤
√
N
Pembangkitan Bilangan Prima (Prime Generation )
Aktivitas untuk mendapatkan bilangan-bilangan prima disebut dengan pembangkitan bilangan
prima. Misalnya, kita ingin mengetahui himpunan bilangan prima yang tidak lebih daripada N.
Pembangkitan Prima Menggunakan Iterasi
Solusi sederhana dari pembangkitan bilangan bilangan prima adalah dengan iterasi dan uji
keprimaan, seperti yang tertera pada Algoritma 5.
Algoritma 5 Pembangkitan Bilangan Prima dengan iterasi dan uji keprimaan.
1:
2:
3:
4:
5:
6:
7:
8:
9:
function SIMPLE P RIME G ENERATION (N)
primeList ← {}
for i ← 2, N do
if IS P RIME S QRT (i) then
primeList ← primeList ∪ {i}
end if
end for
return primeList
end function
Pada metode pembangkitan bilangan prima menggunakan iterasi, kita akan menguji kepri-
maan setiap angka
√ dari 2 hingga N. Uji keprimaan
√
√ suatu bilangan X yang mana X ≤ N memiliki
kompleksitas O( X). Kita tahu bahwa X ≤ N, dan kita akan
√ melakukan pengujian prima
sebanyak N bilangan. Maka kompleksitas akhirnya adalah O(N N).
13