Achmatim.Net



« | »

Algoritma Tercepat Mencetak Bilangan Prima

Beberapa waktu lalu, salah seorang anggota milis phpug bertanya mengenai bagaimana algoritma untuk mencetak bilangan prima dengan cepat. Bilangan prima yang diminta bukan hanya sampai 100 atau 1000, tapi sampai 100juta.

Sieve of Eratosthenes

Setelah mencari di Google, ternyata saya menemukan salah satu algoritma klasik untuk mencetak bilangan prima. Algoritma tersebut disebut sebagai Sieve of Eratosthenes, saya temukan di Wikipedia. Mungkin ini bukan algoritma yang tercepat, tapi setidaknya sudah cukup cepat dibanding jika menggunakan modulus.

Berikut ini algoritma tersebut yang dikutip dari Wikipedia.

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.

Dan berikut ini contoh penerapan algoritma di atas dalam bahasa pemrograman PHP. Script ini sudah ditest untuk menampilkan bilangan prima dibawah 1.000.000 dan berhasil menampilkannya dalam waktu 3 detik.

  1. <?php
  2.  
  3. function bilangan_prima($limit) {
  4. $prima = array();
  5. $prima_awal = array(2,3,5,7);
  6.  
  7. for ($i=2; $i<=$limit; $i++)
  8. $prima[$i] = true;
  9.  
  10. foreach ($prima_awal as $awal) {
  11. for ($i=2*$awal; $i<=$limit; $i+=$awal) {
  12. $prima[$i] = false;
  13. }
  14. }
  15.  
  16. foreach ($prima as $bilangan=>$status) {
  17. if ($status) echo "$bilangan ";
  18. }
  19. }
  20. $start=mktime();
  21.  
  22. bilangan_prima(1000000);
  23.  
  24. $finish=mktime();
  25. $result=$finish-$start;
  26. echo "<br>Time: $result seconds";
  27.  
  28. ?>

Semoga bermanfaat

Posted by on March 28, 2008.

Tags: , ,

Categories: PHP, Umum

13 Responses

  1. cara sieve of Eratosthenes sangat berguna pak, tapi masih ada yg lebih cepat lagi. yaitu sieve of Atkin. saya memakai sieve of Atkin untuk mengerjakan tugas bapak… :mrgreen:

    by meta sanjaya on Sep 23, 2008 at 09:34

  2. :smile:
    hmmmmm……pusing…tapi mudah-mudahan segera ngarti…jadi iri sama si Meta’ katanya ada yang lebih cepat.!walah…..

    patembes last blog post..Domain dan Hosting Gratis

    by patembe on Sep 23, 2008 at 21:34

  3. #meta
    oke deh. besok kita adu dengan temen-temen kamu… tetep semangat!

    #patembe
    yup. coba cari yg lebih cepat, jangan mau kalah. bikin sendiri juga gpp. :D

    by achmatim on Sep 24, 2008 at 20:35

  4. Meta nti ajarin gw yak.,

    udah dapet materi nya sieve of Eratosthenes n sieve of Atkin tp blom ngerti..

    by david on Oct 7, 2008 at 21:44

  5. bagaimana menampilkan bilangan prima pada pemrograman visual basic..??
    tolong sih kirim ke e-mail sy…

    by emilia on Apr 8, 2010 at 16:05

  6. Maaf, scriptnya masih kurang benar.
    Saya tes mencetak bilangan prima cuma sampai 1000 masih ada yang salah. Angka 121, 143, dst (yg bisa dibagi dengan 11) masih bisa tercetak. Angka2 tsb bukanlah prima.
    Mungkin bisa dengan ini koreksinya:

    —————————————————-
    function doOptimusPrime($stop){
    for($i=2;$i<=$stop;$i++){
    $optimusPrime=true;
    for($j=2;$j<=$i-1;$j++){
    if($i % $j == 0){
    $optimusPrime=false;
    }
    }
    if($optimusPrime){
    echo $i.” “;
    }
    }
    }
    doOptimusPrime(1000);
    —————————————————-
    CMIIW :)

    by the coder on Jun 30, 2010 at 15:43

  7. #the coder. Terima kasih atas koreksinya.

    by achmatim on Jul 2, 2010 at 11:03

  8. wah, keren banget ya.. saya suka algoritmanya walaupun agak sulit tuk di pahami

    by syafrin on Dec 24, 2010 at 18:08

  9. postingan yang bermanfaat.. sukses buat kamu

    by liana on Dec 24, 2010 at 18:11

  10. […] sumber […]

    by Algoritma Bilangan Prima Dengan PHP « TeKaJe on Jul 6, 2011 at 08:00

  11. Mantaps…
    Pertanyaan, Apa mamfaat bilangan prima dalam pemograman? apa contoh pengaplikasiaanya?

    cth: bilangan genap/ganjil untuk sortir data, nah klu bilangan prima?

    Salam

    by pakgaol on Sep 14, 2012 at 09:34

  12. pertanyaan bisa dianalogikan dengan “apa manfaat matematika dalam belajar komputer?”. saya kira manfaat adanya bilangan prima bagi kita yang baru belajar algoritma & pemrograman adalah untuk melatih pola pikir bagaimana menyelesaikan suatu permasalahan. dengan menyelesaikan persoalan terkait bilangan prima, maka pola pikir algoritmik kita akan terlatih. dalam aplikasinya, bilangan prima dimanfaatkan sebagai salah satu algoritma enkripsi. ini salah satu artikelnya: http://www.parttimescholar.com/2011/01/prime-numbers-and-encryption.html

    by Achmad Solichin on Sep 25, 2012 at 11:04

  13. susah juga yh ,, oia bisa gk ditambahkan pengertian/penjelasan dari setiap coding yg dibuat ,, heh mkasih :)

    by yuni hsb on Dec 3, 2012 at 20:03

Leave a Reply

 

« | »




Recent Posts


Pages