Prime - Sieve Eratosthenes (Saringan Eratosthenes)

Prime (bilangan prima) adalah salah satu bahasan yang sering keluar dalam olimpiade komputer. Maka perlu bagi kita untuk mempelajari bagaimana mencari bilangan prima dengan cepat, salah satunya dengan cara Sieve Eratosthenes atau Saringan Eratosthenes. (sieve = saringan). Jadi, bagaimana sih algoritma dan pseudocode nya sieve?

Jadi begini lho, sesuai namanya, sieve eratosthenes memiliki algoritma seperti penyaring. Jika di jelaskan secara singkat, sieve akan menyaring semua bilangan dari 2 hingga ke-N, dengan melakukan teknik flag (memberi tanda). mari kita langsung ke TKP.

misalnya di berikan bilangan 1-120. berikut adalah tahap penyaringannya :

1. Penyaringan awal adalah menyaring angka 1. sudah jelas bahwa 1 bukan lah bilangan prima. maka kita dapat mengabaikannya dan memulai perhitungan dari 2-120.
   
2. Penyaringan di mulai dengan mengambil bilangan ke-i yang bukan bilangan komposit (asumsi kan semua bilangan adalah prima, kita blom tau dong mana yg prima atau gak).
   Perhitungan di mulai dari i=2, maka 2 dapat di anggap prima.
   trus bilangan 2 akan di jadikan acuan untuk menyaring 3-120, caranya adalah : jika bilangan ke-j (j=i+1) habis di bagi oleh bilangan ke-i, maka ia bukan bilangan prima dan pantas untuk di CORET. hahaha.
   
   Mari kita simulasi kan :
   2 = prima,
   3 mod 2 = 1, prima.
   4 mod 2 = 0, bukan prima. CORET/nge-flag/menandai.
   5 mod 2 = 1, prima.
   6 mod 2 = 0, bukan prima. CORET.
   dst..
   
   maka kita akan mendapat 2# , 3,5,7,9,11,13,15,17,19,21,..dst.. yang merupakan bilangan prima sampai saat ini (yg belum di CORET)
   
3. Mari kita lanjut ke angka 3. yang merupakan prima seperti yg kita ketahui.
   mulai CORET semua bilangan yg memiliki faktor 3 !!
   
   crot,crot,cret,cret,plung.
   
   maka hasilnya : 2,3# , 5,7,11,13,15,17,19,23,25..dst..
   
4. Mari lanjut ke angka berikutnya. 4 ? lho kok? tadi kita kan udah mencoret semua angka yg memiliki faktor 2, untuk apa lagi kita mencoret bilangan berfaktor 4 yang sudah jelas juga berfaktor 2. Untuk hal ini, kita dapat menyimpulkan bahwa kita tidak akan menjadi kan bilangan komposit sebagai penyaring, kita hanya menggunakan bilangan prima sebagai sieve eratosthenes.
   
5. Lanjut ke-5. 5 adalah prima. mari kita lakukan pembantaian.
   
   sret,sret,ceplak,plung.
   
   hasilnya : 2,3,5# , 7,11,13,17,19,21,23,29,31,37..dst.. sampai 120
   
6. loncati angka 6, kita langsung ke7.
   
   sret,sret. serius ya. hahaha
   
   hasilnya : 2,3,5,7# ,11,13,17,19..dst.. lanjut aja sendiri. coba tulisin 1-120 atau lebih tepatnya tulis 2-120 aja. simulasikan sendiri.
   
7. Simulasikan sampai akar dari N (n disini adalah 120).
   
   Mengapa cuma sampai akar dari N? karena secara teori matematika, kalian hanya perlu mengecek suatu bilangan apakah dia bilangan prima atau tidak dengan cara yang simpel : cukup dengan mengecek apakah dia memiliki faktor antar 2 - akar dari N. jika dia tidak memiliki faktor diantara range tersebut, maka dia perawan, ups, maksudnya bilangan prima.

Begitulah algoritmanya. kalian dapat melihat animasi pencoretannya di http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes, atau kalian ingin membaca artikel bahasa indonesianya, kalian dapat menge-click link ini http://id.wikipedia.org/wiki/Saringan_Eratosthenes

Tadi kurakura juga mengatakan bahwa kurakura akan memberikan pseudocodenya. tapi sebenarnya kurakura tidak suka memberi langsung programmnya. kalian seharusnya mengerjakannya sendiri.

tapi sebagai bantuan saja, makanya kurakura akan membuat pseudocode campur algoritma, bukan program langsungnya. berikut adalah pseudocode campur nya :

declration

  composite is an array 1 to 200 of boolean value.

  i and j are an integer.

  n is an integer.

description

{ 

 n assign with 120

    << N di isi dengan nilai 120 untuk menghitung bilangan prima hinga ke-120

  looping ++ i = 1 to rounded square root from N

    << (rounded = dibulatkan, square root = akar, jadi kita akan looping hingga akar ke-N, lihat alasannya di tahap ke-7)

  {

     if ( i is prime ) then

       << kamu dapat menulisnya dengan not(composite[i])

        looping ++ j = i+1 to N

           << ini dilakukan untuk mengecek i+1 hingga ke-N selama pencoretan.

        {

            if ( j is divisible by i ) then

            {

               << jika angka yg kita cek habis di bagi ama penyaring kita, maka..

               Flag the array composite with index j.

                  << coret angkanya, dalam pseudocode kamu dapat menulisnya dengan composite[j] di isi dengan TRUE. (dalam hal ini kita memberi flag, bahwa bilangan J bukan lah prima, melainkan komposit, maka itu adalah TRUE)

             }

         }

    }

And then, Write all NOT composite number, just write the PRIME

  <<kenapa saya tulis begini saja, supaya kalian agak berpikir! hahaha. codenya kurang lebih seperti ini : looping 2 to N do if NOT composite then write(composite[ ]);

} END

Jadi begitulah. sebenarnya ada yang lebih simpel lagi, coba kalian lihat di Wikipedia bagian bahasa Indonesia, disana ada pseudocode yang lebih simpel di banding ini, namun di sana tidak menggunakan FOR (untuk pascal), melainkan menggunakan while. (mereka menggunakan looping for untuk C dan Java yang kalau di Pascal berarti while :D )

Jadi kurakura programmer ngasih soal buat kalian, coba kalian buat sieve dari for, kemudian di ubah menjadi while, kemudian coba gunakan cara di wikipedia bahasa indonesia. seep? Bye! kurakura mau bobok dulu. hahaha

Bye! Salam KuraKura :)