Minggu, 17 April 2011

Saringan Eratosthenes & Program Bilangan Prima

Assalamu'alaikum wr. wb.




Kali ini saya mau pamer sedikit tentang program buatan saya. Dulu waktu masih semester III saya pernah menempuh mata kuliah Teori Bilangan. Salah satu materi yang saya dapat adalah algoritma untuk mendaftar bilangan-bilangan prima yang kurang dari suatu bilangan bulat tertentu. Metode ini disebut sebagai Saringan Eratosthenes (Sieve of Eratosthenes). Prinsipnya seperti ini
. 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 dan berhenti pada giliran bilangan yang lebih besar dari √n.
  7. Tulis semua bilangan yang belum dicoret pada daftar B.
  8. Selesai. Daftar B memuat semua bilangan prima antara 1 sampai n.
Ilustrasi Saringan Eratosthenes:
Saringan Eratosthenes

Metode lainnya untuk membuat suatu barisan bilangan prima adalah Saringan Euler (Euler's Sieve).
Tapi dengan metode Saringan Eratosthenes ini saya agak kesusahan membuat programnya. Soalnya ilmu saya masih terbatas dalam bahasa C/C++. Jadi saya memakai alternatif lain yang masih efisien untuk bilangan 1.000.000 kebawah. Saya klaim program ini mampu medaftar semua bilangan prima yang kurang dari 1.000.000 dalam waktu 12 detik (jika tidak ada gangguan). Program ini menggunakan uji primalitas (uji keprimaan) kepada setiap biangan yang kurang dari suatu bilangan. Algoritmanya sepeti ini (bagi yang membenci bahasa matematika diharap jangan muntah di depan komputer):
  1. INPUT: i (2<i<∞)
  2. Misal a=2 dan b=√i
  3. Bila i mod a=0 atau a|i maka berhenti dan berarti i adalah bilangan komposit, bila tidak demikian maka a ditambah 1 dan ulangi langkah ini sampai a>b
  4. Bila a>b maka i adalah bilangan prima
Contoh:
INPUT=73
a=2 dan b=√73=8,5440037453175311678716483262397, anggap saja b=9 (b=8 juga sama saja)
73 mod 2=1 a=a+1=2+1=3
73 mod 3=1 a=a+1=3+1=4
73 mod 4=1 a=a+1=4+1=5
73 mod 5=3 a=a+1=5+1=6
73 mod 6=1 a=a+1=6+1=7
73 mod 7=3 a=a+1=7+1=8
73 mod 8=1 a=a+1=8+1=9
73 mod 9=1 a=a+1=9+1=10
73 mod 10=3, berhenti!
karena a sudah melampaui b maka 73 adalah bilangan prima.
Setelah tahu algoritma ini, saya iseng-iseng bikin programnya pake' bahasa C++. Anda bisa mendownload program uji primalitas dengan mengklik download program uji primalitas.
Saat keisengan sudah menguasai hati, siapa yang sanggup menghentikan? Saya pun mengembangkan program ini lebih lanjut menjadi Program Pendaftar Bilangan-bilangan Prima yang Kurang dari n. Namanya kepanjangan ya? Okelah saya singkat menjadi Enumerating Primes Program. Bisa juga didownload disini.
Bikin program ini lebih gampang-gampang susah. Soalnya harus menggabungkan beberapa algoritma dalam satu script code dan otak haruslah kuat. Kalo otak nggak tahan, bisa-bisa jadi kayak temen saya yang namanya Jazuli. LOL.
Ada rencana lagi sih buat bikin program Algoritma Dijkstra. Tapi masih mikir-mikir dulu. Sekian, terima kasih.

Wassalamu'alaikum wr. wb.

NOTE: bagi adik-adik yang belum tahu, mod adalah modulo yaitu operasi sisa bagi. Bilangan Komposit adalah bilangan asli yang lebih dari 1 dan bukan bilangan prima (artinya memiliki faktor lebih dari dua faktor). a|i dibaca "a membagi i" atau "a adalah faktor dari i"
NOTICE: salah memasukkan input bisa menyebabkan hang atau infinite loop. Gunakan komputer minimal pentium 4.

Tidak ada komentar:

Poskan Komentar

Apabila anda temukan segala bentuk kesalahan atau kekurangan di dalam blog ini silahkan beritahu saya dan ikut mengembangkan blog ini. Bisa kirim pesan via email di zamlahani@gmail.com atau lewat komentar di dalam postingan blog. Terima kasih. ^_^

Kirimi Post via Email