My first Magazine pemrograman-kompetitif-dasar | Page 24

2 Matematika Diskret Dasar
Sieve of Eratosthenes
Terdapat solusi yang lebih cepat untuk membangkitkan bilangan prima, yaitu saringan
Eratosthenes, atau Sieve of Eratosthenes. Ide utama utama dari algoritma ini adalah mengeli-
minasi bilangan-bilangan dari calon bilangan prima, yaitu bilangan komposit.
Kita tahu bahwa suatu bilangan komposit c dapat dinyatakan sebagai c = p × q, dengan p
suatu bilangan prima. Seandainya kita mengetahui suatu bilangan prima, kita dapat mengeliminasi
kelipatan-kelipatan bilangan tersebut dari calon bilangan prima.
Contoh: jika diketahui 7 adalah bilangan prima, maka 14, 21, 28, ... dieliminasi dari calon
bilangan prima.
Berikut prosedur dari Sieve of Eratosthenes:
1. Awalnya seluruh bilangan bulat dari 2 hingga N belum dieliminasi.
2. Lakukan iterasi dari 2 hingga N:
a) Jika bilangan ini belum dieliminasi, artinya bilangan ini merupakan bilangan prima.
b) Lakukan iterasi untuk mengeliminasi kelipatan bilangan tersebut.
Algoritma 6 menunjukkan implementasi Sieve of Eratosthenes. Untuk mengimplementasikan-
nya, kita dapat menggunakan array boolean untuk menyimpan informasi apakah suatu bilangan
telah tereliminasi. Untuk mencari bilangan prima yang ≤ N, diperlukan memori sebesar O(N).
Untuk kompleksitas waktu, perhitungan matematis 7 membuktikan bahwa solusi bekerja dalam
O(N log (log N)).
Algoritma 6 Sieve of Eratosthenes
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
function SIEVE O F E RATOSTHENES (N)
eleminated ← new boolean[N + 1]
FILL A RRAY (eleminated, f alse)
primeList ← {}
for i ← 2, N do
if not eleminated[i] then
primeList ← primeList ∪ {i}
j ← i × i
while j ≤ n do
eleminated[ j] ← true
j ← j + i
end while
end if
end for
return primeList
end function
. Siapkan array boolean eleminated
. Isi seluruh elemen eleminated dengan f alse
Perhatikan baris ke-8 yang berisi j = i × i. Di sini, j menyatakan kelipatan i yang akan
dieliminasi. Perhatikan bahwa j dimulai dari i × i, bukan 2i. Alasannya adalah 2i, 3i, 4i, ..., (i − 1)i
pasti sudah tereliminasi pada iterasi-iterasi sebelumnya.
14