Sibudi </>

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.

04. September 2012 by Sibudi
Categories: Java | Tags: Java, Snippet, Tutorial | 6 comments