Bilangan prima adalah sebuah bilangan bulat positif yang lebih besar dari satu dan tidak ada bilangan bulat positif lain yang dapat membagi habis selain satu dan bilangan itu sendiri. Contoh : 2, 3, 5, 7, 11, 13, 17, ....
Ada beberapa cara untuk menemukan bilangan prima, antara lain sebagai berikut :
- Metode Sieve of Eratosthenes (Saringan Eratosthenes)
Saringan Eratosthenes adalah suatu cara untuk menemukan bilangan prima diantara bilangan 1 dan bilangan n. Saringan ini ditemukan oleh Eratosthenes, seorang ilmuan dari Yunani Kuno. Saringan Eratosthenes merupakan cara yang paling sederhana untuk menemukan bilangan prima.
Langkah - langkah menemukan bilangan prima dengan saringan Eratosthenes adalah sebagai berikut :
1. Menulis semua bilangan, mulai dari bilangan 1 sampai n pada daftar A.
2. Membuat daftar B yang masih kosong.
3. Mencoret bilangan 1 dari daftar A.
4. Menulis bilangan 2 pada daftar B, lalu mencoret semua kelipatan bilangan dua dari
daftar A.
daftar A.
5. Bilangan pertama yang belum tercoret dari daftar A (misal bilangan 3) merupaka bilangan
prima . Kemudian, menuliskan bilangan 3 pada daftar B dan mencoret bilangan 3 serta
kelipatannya dari daftar A.
prima . Kemudian, menuliskan bilangan 3 pada daftar B dan mencoret bilangan 3 serta
kelipatannya dari daftar A.
6. Mengulangi langkah 5 hingga semua bilangan tercoret dari daftar A.
7. Setelah selesai, semua bilangan pada daftar B merupakan bilangan prima.
- Metode Mersenne
Bilangan prima yang ditemukan oleh Mersenne disebut dengan bilangan prima Mersenne. Bilangan prima Mersenne dirumuskan
dengan n adalah bilangan prima. Contoh : untuk n = 5 maka,
Jadi, 31 merupakan bilangan prima.
- Menggunakan Program Maple
Maple merupakan sebuah software yang biasa digunakan untuk membantu dalam perhitungan matematika. Berikut contoh menentukan bilangan prima menggunakan program Maple 11 :
- Untuk menentukan bilangan prima lebih besar dari bilangan 1000, maka pada worksheet Maple 11 ditulis,
> nextprime(1001);
1009
Jadi, bilangan prima lebih besar dari bilangan 1000 adalah bilangan 1009.
-Untuk menentukan bilangan prima kurang dari bilangan 1000, maka pada worksheet Maple 11 ditulis,
> prevprime(1000);
997
Jadi, bilangan prima kurang dari bilangan 1000 adalah bilangan 997.
-Untuk melakukan pengecekan, apakah bilangan prima yang ditemukan benar merupakan bilangan prima
pada worksheet Maple 11 ditulis,
> isprime(1009);
true
> isprime(997);
true
Jadi, benar bahwa bilangan 1009 dan bilangan 997 merupakan bilangan prima.
Referensi :
Klima, Richard E., Sigmo, Neil, & Stitzinger, Ernest. (1999). Applications of Abstract Algebra with Maple. New York : CRC Press LLC.
Rosen, Kenneth H. (2005). Elementary Number Theory and Its Application. Fifth Edition. New Jersey : Addison Wesley Publishing Company.
Wikipedia. (2010). Saringan Eratosthenes. http://id.wikipedia.org/wiki/SaringanEratosthenes. Tanggal akses 17 Maret 2010 pukul 12.04.
