Bilangan Prima

Menurut Rosen (1993: 64) bilangan prima didefinisikan sebagai berikut.
Definisi
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. Bilangan bulat positif yang lebih besar dari satu dan bukan bilangan prima disebut bilangan komposit.
Untuk lebih jelasnya, diberikan contoh berikut.
Contoh
7 merupakan bilangan prima karena hanya habis dibagi oleh 1 dan 7.
8 merupakan bilangan komposit karena 8 > 1 dan bukan bilangan prima.

Bilangan prima dapat ditemukan dengan menggunakan cara-cara berikut :
 1. Saringan Eratosthenes
Saringan Eratosthenes adalah suatu cara untuk menemukan semua bilangan prima diantara 1 dan bilangan n. Saringan ini ditemukan oleh Eratosthenes, seorang ilmuwan Yunani kuno. Cara ini merupakan cara paling sederhana dan paling cepat untuk menemukan bilangan prima.
 Langkah-langkah saringan Eratosthenes :
a. Menulis semua bilangan, mulai dari 1 sampai n pada daftar A.
b. Membuat daftar B yang masih kosong.
c. Mencoret bilangan 1 dari daftar A.
d. Menulis bilangan 2 pada daftar B. Lalu mencoret bilangan 2 dan semua kelipatannya dari daftar A.
e. Menuliskan bilangan pertama yang belum tercoret dari daftar A di daftar B, lalu mencoret bilangan tersebut dan semua kelipatannya dari daftar A.
f. Mengulangi langkah ke-5 hingga semua bilangan di daftar A tercoret. Setelah selesai, semua bilangan di daftar B adalah bilangan prima.
Ilustrasi pencarian bilangan prima menggunakan saringan Eratosthenes diberikan pada contoh berikut :

Contoh

Akan dicari bilangan prima kurang dari n = 20.

a.      Menulis semua bilangan, mulai dari 1 sampai 20  pada daftar A.

b.      Membuat daftar B yang masih kosong.

 

c.      Mencoret bilangan 1 dari daftar A.

d.      Menulis bilangan 2 pada daftar B. Lalu mencoret bilangan 2 dan semua kelipatannya dari daftar A.

e.      Menuliskan bilangan pertama yang belum tercoret dari daftar A di daftar B, lalu mencoret bilangan tersebut  dan semua kelipatannya dari daftar A.  

  Mengulangi langkah 5 hingga semua bilangan di daftar A tercoret.  

Jadi, bilangan pada daftar B merupakan bilangan prima kurang dari 20 yaitu 2, 3, 5, 7, 11, 13, 17 dan 19.

2.     Bilangan Prima Mersenne

(http://id.wikipedia.org/wiki/Bilangan_prima_mersenne)

Bilangan prima Mersenne dirumuskan M_n = 2ⁿ – 1, dengan n adalah bilangan prima. Bilangan prima Mersenne terbesar yang diketahui sampai saat ini terdiri dari 9.808.358 digit.

Berikut ini contoh pencarian bilangan prima Mersenne.

 Contoh

Untuk n = 5 maka, M₅ = 2⁵ – 1 = 31. Jadi, M₅ = 31 merupakan bilangan prima.