01 January 2009

Mencari Bilangan Prima dengan Aplikasi Java

Suatu kali ada seseorang yang datang kepada saya dengan maksud ingin memulai belajar Java, ia banyak bertanya kepada saya masalah Java dan perkembangannya. Salah satu pertanyaan yang muncul dari salah satu cerita adalah bagaimana membuat sebuah program Java yang mampu menghasilkan deretan bilangan prima?, yang jadi masalah adalah, saya sendiri saat itu sudah lupa apa perngertian bilangan prima, sehingga kita kesulitan untuk membuat programnya. he..he..he..(alasan...!!!).

Kemarin saya teringat kejadian itu, dan segera saya googling mencari tahu pengertian bilangan prima. Dari wikipedia versi indonesia saya mendapatkan pengertian bilangan prima secara baku, kemudian saya coba memahami arti sebenarnya pengertian bilangan prima. Bilangan prima adalah Suatu bilangan asli yang dimulai dari 2, dimana bilangan ini adalah bilangan yang tidak habis dibagi dengan bilangan apapun dibawahnya kecuali dibagi dengan satu dan bilangan itu sendiri. Begitu pemahaman yang saya ambil dari pengertian bilangan prima. Mari kita coba ambil sebuah angka dan coba memeriksanya dengan pemahaman yang saya dapat, misal kita ambil angka 15, apakah angka 15 adalah bilangan prima ? Pemeriksaan kita, akan kita urutkan seperti ini :

  1. Apakah 15 lebih besar sama dengan 2 (15 >= 2 ) ?, sebab salah syarat pertama bilangan prima adalah bilangan asli yang dimulai dari 2.
  2. Apakah 15 akan habis dibagi dengan bilangan-bilangan yang dimulai dari 2 sampai dengan 14 ?, sebab syarat bilangan prima yang lain adalah bilangan yang tidak habis dibagi dengan bilangan apapun dibawahnya kecuali satu dan dirinya sendiri.

Ok kita mulai pemeriksaan kita satu demi satu, untuk pemeriksaan pada tahap yang pertama 15 lolos, artinya 15 memang lebih besar dari pada 2, kemudian kita lanjutkan dengan pemeriksaan tahao ke dua. Apakah 15 habis jika di bagi dengan 2, hasilnya 15 tidak habis di bagi dengan 2, karena 15/2= 7 dan sisa 1. Pemeriksaan kita lanjutkan dengan membagi lagi 15 dengan 3, pada pembagian yang ini 15 jelas bukanlah bilangan prima, sebab 15 dibagi dengan 3, habis, 15/3 = 5, habis tidak ada sisa. Jelas 15 bukanlah bilangan prima sebab 15 habis di bagi dengan 3.

Sekarang kita akan ambil satu bilangan lagi yaitu 17, dan kita akan coba periksa lagi dengan metode yang sama dengan ketika kita mencari bilangan prima untuk angka 15. Untuk pemeriksaan pertama bilangan 17 pasti lolos sebab 17 lebih besar dari pada 2, dan untuk pemeriksaan ke dua, kita lihat seperti gambar di bawah ini :

17 / 2 = 8 sisa 1
17 / 3 = 5 sisa 2
17 / 4 = 4 sisa 1
17 / 5 = 3 sisa 1
17 / 6 = 2 sisa 5
17 / 7 = 2 sisa 3
17 / 8 = 2 sisa 1
17 / 9 = 1 sisa 8
17 / 10 = 1 sisa 7
17 / 11 = 1 sisa 6
17 / 12 = 1 sisa 5
17 / 13 = 1 sisa 4
17 / 14 = 1 sisa 3
17 / 15 = 1 sisa 2
17 / 16 = 1 sisa 1

Pada gambar diatas, kita bisa melihat bahwa 17 itu selalu sisa jika dibagi dengan bilangan apapun dibawah bilangan 17 kecuali 1 dan 17 itu sendiri. Dari situ kita bisa simpulkan bahwa 17 adalah bilangan prima.

Bagaimana jika dengan tahap – tahap tersebut kita mencoba membuat aplikasi java yang mampu memeriksa sebuah bilangan apakah bilangan tersebut merupakan bilangan prima atau bukan. Ok, jika kita akan membuat sebuah program yang mampu memeriksa sebuah bilangan adalah bilangan prima atau bukan, seperti inilah kode-kode progamnya:

package org.mojo.blog.app.integer; //ignore this, if this program is not on package

public class isPrimeApplication {

public static void main(String[] args) {
int valueToCheck = 17; // value to check
boolean isPrime = false;
if (valueToCheck >= 2) {
isPrime = true; // first check and assume it's prime number
// try divide valueToCheck
// with all number less than it self
// and begining from 2
for (int i = 2; i < valueToCheck; i++) {
if (valueToCheck % i == 0) {
//if divides exactly so stop the loop and it must be not prime
isPrime = false;
break; // no need to check again
}
}
}
System.out.println("is " + valueToCheck + " Prime ? ");
System.out.println("the answer is " + isPrime);
}
}

Dalam kode di atas kita bisa melihat bahwa kita punya dua variabel, valueToCheck dan isPrime, sementara flow process kita buat mirip skenario tahap-tahap pengecekan, dimana :

  1. if(valueToCheck > = 2) adalah pengecekan tahap pertama, dimana semua angka yang masuk dalam blok ini akan sementara kita asumsikan adalah bilangan prima (isPrime = true).
  2. for (int i = 2; i <>Kemudian kita melakukan looping mulai dari 2 sampai dengan bilangan yang ingin di cek diambil 1 (valueToCheck – 1 ). Kemudian kita melakukan pemeriksaan apabila dari rangkaian looping cek tsb ada yang menghasilkan pembagian dengan tidak ada sisa, maka kita sudahi pemeriksaan, dan bilangan tsb pasti bukan bilangan prima.

Hmm, bagaimana jika program tsb kita kembangkan lagi menjadi sebuah program yang mampu mencari bilangan-bilangan prima dari suatu range bilangan, misal mencari bilangan-bilangan prima yang lebih kecil dari 50. Sepertinya secara logika kita bisa membuatnya dengan hanya menambahkan suatu looping saja sebelum looping yang ada di atas. Ok mari kita coba, perhatikan kode-kode berikut ini.

package org.mojo.blog.app.integer; //ignore this, if this program is not on package

public class PrimeAdvance {

public static void main(String[] args) {
// int valueToCheck = 17; // value to check
int nRange = 50;
boolean isPrime = false;

for (int i = 2; i <= nRange; i++) {
if (i >= 2) {
isPrime = true; // first check and assume it's prime number
// try divide valueToCheck
// with all number less than it self
// and begining from 2
for (int j = 2; j < i; j++) {
if (i % j == 0) {
//if divides exactly so stop the loop and it must be not prime
isPrime = false;
break; // no need to check again
}
}
}
if(isPrime){
System.out.println(i);}
}
//System.out.println("is " + valueToCheck + " Prime ? ");
//System.out.println("the answer is " + isPrime);
}
}

Pada kode diatas kita bisa melihat bahwa kita cukup menambahkan logika satu buah looping diatas looping yang ada sebelumnya, kemudian kita menambahkan baris, jika i adalah bilangan prima maka cetaklah ke atas konsol. Namun baris yang memerintahkan program untuk mencetak ke atas konsol kita letakkan di dalam looping range data yang ingin kita periksa.

Demikianlah, sedikit cerita tentang eksplorasi keingintahuan saya terhadap bilangan prima, yang berdasarkan senggolan cerita dari seorang teman. Silahkan di gunakan jika memang bermanfaat dan silahkan juga dikembangkan jika memang anda mempunyai ide-ide baru yang lain.

Untuk lebih memahami bilangan prima itu sendiri, berikut ini adalah link program java dimana dalam setiap proses looping-nya saya menambahkan cetakan ke konsol.

Semoga bermanfaat

Menteng 01 Januari 2009

josescalia

12 comments:

Anonymous said...

Halo mas, fungsi mengecek prima buatan anda sangat lambat. Coba kalo valueToCheck = (1<<30)-1;

visit my blog:
algojava.blogspot.com

JoseScalia said...

[Quote]
Halo mas, fungsi mengecek prima buatan anda sangat lambat. Coba kalo valueToCheck = (1<<30)-1;

[/Quote]
Terima kasih...dah mo mengunjungi blog ini...

Anonymous said...

Intinya gak perlu ada pengecekan mulai dari 1-n bilangan, cukup dibagi dengan 1-9 saja.

Blognya Yan said...

blognya bagus mas, tapi yang lebih simple bisa gak?

He3x...maklum masih maba + new blogger gitu ^_^!

Blognya Yan said...

ada cara yang lebih sederhana gak mas?


BTW, postingannya top abis, nambah pengetahuan banget. sukses yach!!!

JoseScalia said...

Buat Yan...

Ini juga simple dan sederhana kok..makanya banyak yang protes, padahal ini cuma salah satu pembuktian dari konsep masalah yang bisa kita komputasikan...

Terima kasih telah mengunjungi blog ini...

Anonymous said...

Terima kasih mas, tutorialnya membantu :)

Oh ya, saya masih bingung dengan for nested.

Alur pembacaannya gimna ya, mas?

Mhon bantuannya :)

JoseScalia said...

Buat Fanjavaakhamd:

For Nested yang dilakukan pada program tersebut ditujukan :
1. untuk mencari satu demi satu nilai yang termasuk dalam range dalam hal ini mulai 1 s/d 50
2. setiap nilai yang masuk range akan di lakukan pemeriksaan pembagian, dengan nilai pembagian yang dimulai dari 1 s/d nilai pertama yang didapat..

FYI:
Algoritma ini cuma salah satu konsep mengkonsepkan apa yang ada dalam hitungan2 teori untuk bisa di masukkan kedalam algoritma pemrogaman, masih ada cara lain juga untuk mencari bilangan prima yang mungkin lebih cepat dan lebih mudah dipahami

Terima kasih telah mengunjungi blog ini.

Josescalia

tutorial-computer said...

ini aku dapat tutorial mengenai bilangan prima yang di input limitnya dari http://tutorial-computer.com/index.php?option=sourcecode_java_creating_primes

semoga membantu

Anonymous said...

wah mas kok pas saya coba ada error parsing gt,
mksdny ap y?

Anonymous said...

Keminter..
coba klo nilai yang dimasukkan 2, gk bakal di cek nilainya coz dia cuma ngecek nilai yang kurang dari bilangan itu sendiri.

Agung Imamudin said...

saya waktu coba juga ada yang error mas,, gimana
mampir blog saya sebentar mas,,
agung