Bagaimana Mencari Bilangan Prima?
Salah satu pertanyaan paling penting dalam dunia Matematika adalah
menentukan apakah suatu angka merupakan bilangan prima atau tidak. Topik
bilangan prima ini juga menjadi salah satu dari tujuh masalah utama
dalam bidang Matematika (Millennium Prize Problems),
yaitu Riemann hypothesis. Orang pertama yang sanggup memecahkan salah
satunya akan mendapat hadiah US$1,000,000 dari Clay Mathematics
Institute. Sampai sekarang masih tersisa enam soal yang belum
terpecahkan termasuk Riemann hypothesis yang bila dapat dipecahkan dapat
menguak pola distribusi bilangan prima.
Bilangan prima adalah bilangan asli yang lebih besar dari 1 dan hanya
memiliki dua faktor (pembagi) yaitu 1 dan bilangan itu sendiri. Contoh
bilangan prima adalah 7, yang hanya memiliki dua faktor yaitu 1 dan 7.
Sebaliknya, 6 bukan merupakan bilangan prima karena memiliki
faktor-faktor 1, 2, 3, dan 6. Bilangan selain bilangan prima disebut
bilangan komposit.
Bilangan prima sangat menarik karena aturan untuk menentukan bilangan
prima sudah sangat jelas dan mudah dipahami, namun belum ada rumus atau
persamaan yang mudah untuk menentukan apakah sebuah angka merupakan
bilangan prima atau bukan.
Dalam tutorial kali ini akan dibahas bagaimana menentukan sebuah
angka adalah prima atau bukan dengan menggunakan bahasa pemrograman
Java. Cara yang paling sederhana adalah dengan mencoba membagi sebuah
bilangan dengan setiap bilangan dari 2 sampai ke bilangan n – 1. Jika
ada satu bilangan saja yang dapat habis membagi berarti bilangan
tersebut bukan prima.
boolean isPrime (int n) {
for (int i=2; i<n; i++)
if (n % i == 0)
return false;
return true;
}
Angka 2 adalah satu-satunya bilangan prima genap, jadi tidak perlu
dipusingkan dengan mencobanya. Kode di atas mungkin cukup untuk mencari
bilangan kecil, tapi kita butuh algoritma yang lebih cepat/mangkus untuk
mencari bilangan besar. Kita tidak perlu mencari dari 2 sampai bilangan
n, tapi cukup sampai n/2. Karena jika angka 2 habis membagi n, dapat
dipastikan n/2 juga akan habis membagi n.
boolean isPrime (int n) {
for (int i=2; i*2<n; i++)
if (n % i == 0)
return false;
return true;
}
Masih belum cukup cepat? Algoritma di atas bisa dioptimalkan lagi,
yaitu dengan hanya memeriksa bilangan ganjil saja, karena semua bilangan
genap pasti habis dibagi 2. Kemudian kita bisa efisienkan percobaan di
atas dengan hanya memeriksa pembaginya sampai ke akar kuadrat dari
bilangan n (dengan pembulatan ke bawah). Karena jika kita menderetkan
semua faktor dari sebuah bilangan, akar kuadratnya pasti selalu berada
di tengah-tengah deret tersebut. Misal faktor dari 81 adalah 1, 3, 9,
27, 81. Akar kuadrat dari 81 adalah 9, terletak tepat di tengah-tengah
deret tersebut. Tidak perlu diperiksa setengah bagian setelah akar
kuadrat karena pasti sudah ketahuan prima atau bukan.
boolean isPrime (long n) {
if (n % 2 == 0) return false;
for (long i=3; i*i<=n; i+=2)
if (n % i == 0)
return false;
return true;
}
Seperti terlihat pada potongan kode di atas, kita hanya memeriksa
sampai ke akar kuadrat dari bilangan n dan hanya memproses bilangan
ganjil. Dengan algoritma ini, program kita pasti mengalami peningkatan
yang signifikan. Terutama ketika bekerja dengan angka yang sangat besar,
itulah kenapa digunakan tipe data long.
Sebenarnya ada satu lagi metode yang lebih mangkus yang disebut The Sieve of Eratosthenes.
Namun kurang cocok dengan kebutuhan karena metode ini digunakan untuk
mencari semua bilangan prima dari 2 sampai ke bilangan n.
.JPG)
