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 dan http://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 X
itu 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 sampai X-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
