Bilangan prima termasuk bilangan yang cukup
unik, kita sudah mempelajari bilangan ini sejak masuk sekolah dasar.
Beberapa referensi
yang penulis dapat menyatakan bahwa bilangan prima merupakan bilangan positif
yang hanya bisa dibagi oleh tepat 2 pembagi, yaitu angka 1 dan angka tersebut
sendiri. Ada juga yang menyatakan sebagai suatu bilangan yang hanya bisa dibagi
oleh dirinya sendiri tanpa menyertakan angka 1.
Contoh: 2, 3, 5, 7,
11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,
97 dan seterusnya.
Teori selanjutnya
silakan baca http://en.wikipedia.org/wiki/Prime_number danhttp://mathworld.wolfram.com/PrimeNumber.html.
Dalam logika
pemrograman, kita cuma perlu memperhatikan mulai angka 2 dan seterusnya. Angka
0 jelas tidak mungkin, karena bilangan ini dibagi angka berapapun akan
menghasilkan angka 0. Dan angka 1 juga kita abaikan saja, sebab angka 1 hanya
bisa dibagi oleh dirinya sendiri, padahal bilangan prima itu syarat utamanya
bisa dibagi oleh 2 bilangan natural yang nyata, yaitu angka 1 dan dirinya
sendiri. (Note: bisa dibagi ini dalam artian menghasilkan bilangan bulat
positif, bukan bilangan pecahan.)
Berikutnya akan
penulis ilustrasikan contoh pembagiannya, dimana kita sepakati bahwa angka
pembagi tidak melibatkan angka 1.
2: hanya bisa
dibagi 2.
3: hanya bisa
dibagi 3.
4: bisa dibagi 2
dan 4 (lebih dari 1 pembagian, maka tidak termasuk bilangan prima).
5: hanya bisa
dibagi 5.
6: bisa dibagi 2,3,
dan 6 (bukan bilangan prima).
Dan seterusnya.
Misalkan diketahui
sebuah bilangan X, bagaimana cara menentukan bahwa bilangan Xitu
termasuk bilangan prima atau bukan?
Asumsi: X adalah
bilangan yang lebih besar dari 2
Berarti
bilangan-bilangan yang akan menjadi pembagi adalah mulai angka 2 sampaiX-1.
Jika bilangan X
bisa dibagi oleh minimal salah satu dari bilangan-bilangan mulai 2 sampai X-1,
maka dapat dikatakan bahwa bilangan X adalah bukan bilangan prima.
Contoh: 9
Bilangan sebagai
pembagi adalah 2 3 4 5 6 7 8
Untuk mengetahui
bahwa suatu bilangan bisa dibagi atau tidak, paling mudah kita menggunakan
bantuan mod, yang menyatakan sisa hasil bagi. Jika sisa hasil bagi 0
berarti bisa dibagi.
Kembali ke contoh.
9 mod 2 = 1 (hasil
bukan 0, artinya tidak habis/bisa dibagi), lanjutkan,
9 mod 3 =0 (sudah
cukup untuk menyimpulkan bahwa 9 adalah bukan bilangan prima.)
Tidak perlu kita
uji dengan membagi 9 dengan angka 4 dan seterusnya.
Contoh lain: 11
11 mod 2 = 1
11 mod 3 = 2
11 mod 4 = 3
11 mod 5 = 1
11 mod 6 = 5
11 mod 7 = 4
11 mod 8 = 3
11 mod 9 = 2
11 mod 10 = 1
Tidak ada yang
menghasilkan angka 0, berarti 11 termasuk bilangan prima.
Sekarang kita coba
dengan algoritma pemrogramannya.
KAMUS
i : integer
bil : integer
prima : boolean
ALGORITMA
prima ← false
input (bil)
if (bil=2) then
prima ← true
else
for i ← 2 to bil-1 do
if (bil mod i = 0) then
prima ← false
exit for // keluar dari looping
else
prima ← true
endif
endfor
endif
if (prima) then // prima=true
output ("Bilangan Prima")
else
output ("Bukan Bilangan Prima")
endif
Logika di atas bisa
digunakan kalau kita ingin memeriksa hanya pada satu bilangan tertentu saja.
Bagaimana kalau
soal kita kembangkan, menampilkan bilangan prima dari bilangan sekian sampai
sekian. Maka tinggal kita kombinasikan dengan looping juga.
Tags
informatika