Bilangan Prima

Dalam matematika, bilangan prima adalah bilangan asli yang lebih besar dari 1, yang faktor pembaginya adalah 1 dan bilangan itu sendiri. 2 dan 3 adalah bilangan prima. 4 bukan bilangan prima karena 4 bisa dibagi 2. Sepuluh bilangan prima yang pertama adalah 2, 3, 5, 7, 11, 13, 17, 19, 23 dan 29.

Jika suatu bilangan yang lebih besar dari satu bukan bilangan prima, maka bilangan itu disebut bilangan komposit. Cara paling sederhana untuk menentukan bilangan prima yang lebih kecil dari bilangan tertentu adalah dengan menggunakan Saringan Eratosthenes.

Saringan Eratosthenes

Saringan Eratosthenes adalah suatu cara untuk menemukan semua bilangan Prima diantara 1 dan suatu angka n. Saringan ini ditemukan oleh Eratothenes, seorang ilmuwan Yunani Kuno. Cara ini merupakan cara paling sederhana dan paling cepat untuk menemukan bilangan prima, sebelum Saringan Atkin ditemukan pada tahun 2004. Saringan Atkin merupakan cara yang lebih cepat namun lebih rumit dibandingkan dengan Saringan Eratosthenes.

Langkah-Langkah Saringan Eratosthenes

Misalkan kita hendak menemukan semua bilangan prima di antara 1 sampai suatu bilangan bulat n.

  1. Tulis semua bilangan, mulai dari 1 sampai n. Misalkan ini adalah daftar A.
  2. Buat suatu daftar yang masih kosong, sebut saja daftar B.
  3. Coret bilangan 1 dari daftar A.
  4. Lalu tulis 2 pada daftar B. Lalu coret 2 dan semua kelipatannya dari daftar A
  5. Bilangan pertama yang belum tercoret dari daftar A (misalnya 3) adalah bilangan prima. Tulis bilangan ini di daftar B, lalu coret bilangan ini dan semua kelipatannya dari daftar A.
  6. Ulangi langkah 4 sampai semua bilangan di daftar A sudah tercoret.

Setelah selesai, semua bilangan di daftar B adalah bilangan prima.

Animasi saringan Eratosthenes dari 1 sampai n=120. Daftar A (kiri) dan daftar B (kanan).
Bilangan yang sudah diwarnai artinya sudah dicoret

Saringan Eratosthenes dan pemrograman

Saringan Eratosthenes dapat dimanfaatkan dalam pemrograman. Sebuah program dapat menampilkan deretan bilangan prima yang ada di antara 1 sampai n dengan memanfaatkan ide saringan Eratosthenes. Berikut ini adalah sebuah potongan kode dalam bahasa pemrograman Java yang mencetak bilangan prima di antara 1 sampai n=120.

Potongan Script Java Pencetakan Bilangan Prima
int n=120; //batas atas n dapat diganti dengan bilangan bulat lainnya
boolean[] prima=new boolean[n+1];

for(int i=0; i<=n; i++)
	prima[i]=true;        //set seluruh array menjadi true
prima[0]=prima[1]=false;     //0 dan 1 bukan bil. prima
int akarN=Math.sqrt(n);      //akar kuadrat dari n

//coret bilangan yang bukan prima
for(int i=2; i<=akarN; i++) {
	if (prima[i]) {
	     for (int j=i*i; j<=n; j=j+i)
                 prima[j]=false;
	}
}

//tampilkan seluruh bilangan prima
for(int i=0; i<n; i++) {
	if (prima[i])
		System.out.print(i+ "\t");
}

Bilangan Prima Terbesar

Secara matematis, tidak ada “bilangan prima yang terbesar”, karena jumlah bilangan prima adalah tak terhingga. Bilangan Prima yang terbesar yang diketahui per Agustus 2007 adalah 232.582.657 − 1. Bilangan ini mempunyai 9.808.358 digit  dan merupakan bilangan prima Marsenne yang ke-44. M32582657 (demikian notasi penulisan bilangan prima Mersenne ke-44) ditemukan oleh Curtis Cooper dan Steven Boone pada 4 September 2006 yang merupakan profesor-profesor dari University of Central Missouri bekerja sama dengan puluhan ribu anggota lainnya dari proyek GIMPS.

 

About these ads

About labarasi

Guru Matematika

Posted on Januari 26, 2011, in Matematika and tagged , , , , , , , , , , . Bookmark the permalink. 16 Komentar.

  1. bener2 belajar matematika di sini
    Salam kenal…. :)

  2. Ikut belajar bilangan prima Mas…
    Makasih sudah berkunjung ke Blog Saya…

  3. Terima kasih Pak Marsudiyanto atas kunjungannya

  4. belajar agy biar pinter .. heheheee

    salam :)

  5. waduh,,,belajar dulu ahhh…. :)

  6. Animasinya menarik Pak, ..mau coba dulu ya Pak.

  7. ‘tu pelajaran SMP ya pak ? apa lagi kalo b’lajarnya di temeni ama makanan khas Betawi – Ikan Gabus …. kapan ni’ maen2 ke Jkt di tg lho …

  8. wah, sayang sekali kenapa gak pas SMA dulu dapet kayak ginian. kan jadi tambah enak belajar matematikanya,,
    hihi.. :D

  9. makase Bang, lumayan buat belajar wat bsk pengen UAS

  10. wah pas lagi UTS langsung bisa :D

  11. makasih atas infonya

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Logout / Ubah )

Twitter picture

You are commenting using your Twitter account. Logout / Ubah )

Facebook photo

You are commenting using your Facebook account. Logout / Ubah )

Google+ photo

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

  • Back Link

  • Ikuti

    Get every new post delivered to your Inbox.

    Bergabunglah dengan 110 pengikut lainnya.

    %d bloggers like this: