Mencari Deret Bilangan Prima Menggunakan Algoritma Sieve of Eratosthenes

Dalam artikel Cara Cepat Menentukan Bilangan Prima, telah dibahas algoritma untuk mencari apakah suatu bilangan merupakan bilangan prima atau bukan. Nah, dalam artikel ini akan dibahas mengenai cara yang cukup efektif untuk mencari deret bilangan prima dalam range tertentu. Algoritma yang akan dipakai adalah Sieve of Eratosthenes.

Sekilas Sieve of Eratosthenes

Sieve of Eratosthene adalah algoritma sederhana dan cukup kuno yang digunakan untuk mencari semua bilangan prima hingga range tertentu. Berikut adalah langkah-langkah untuk mencari deret bilangan prima dengan batas range 120. Silakan langsung dicoba dioret-oret di kertas ya, smile

  1. Catat semua bilangan dari 1-120.
  2. Karena angka 1 tidak memenuhi definisi bilangan prima, maka coret angka tersebut. Kemudian, angka berikutnya, yaitu angka 2, akan dianggap sebagai bilangan prima.
  3. Coret semua bilangan yang merupakan kelipatan dari bilangan prima terbesar yang diketahui (pada langkah pertama berarti angka 2). Bilangan tersebut pasti bukan bilangan prima.
  4. Bilangan yang belum tercoret setelah angka prima terbesar yang diketahui (pada langkah pertama berarti angka 3), pasti bilangan prima.
  5. Ulangi langkah 3 dan 4 hingga tidak ada lagi bilangan yang lebih besar dari bilangan prima terbesar yang diketahui yang belum tercoret.

Hehe, maaf, penjelasannya agak ribet. Silakan lihat ilustrasi dari wikipedia[1] berikut, semoga dapat membantu memahaminya.

Berikut contoh diagram flowchart SOE. Maaf agak berantakan.

Flowchart Pencarian Bilangan Prima Menggunakan Algoritma Sieve of Eratosthenes

Berikut contoh script SOE dalam javascript. Script berikut merupakan hasil konversi script SOE dalam bahasa C dari Marcus Kazmierczak[2]

function SOE(maxRange)
{
    var START = 3;
    var STOP = maxRange;
    var nap;    // not-a-prime, boolean untuk mengetahui apakah merupakan bilangan prima
    var c;      // untuk menyimpan jumlah bilangan prima, sebagai pointer untuk menyimpan bilangan prima ke-n
    var prime = new Array();    // array untuk menyimpan bilangan prima

    prime[0] = 2;   // dimulai dari bilangan 2 adalah prima
    c = 1;          // jumlah bilangan prima saat ini = 1

    // cukup mengecek bilangan ganjil
    for (var num=START; num num) { break; }
            // bisa juga pakai cara ini:
            // hentikan looping bila bilangan prima ke-i lebih besar dari akar num
            //if (prime[i] > Math.sqrt(num)) { break; }
        }

        // jika num adalah bilangan prima, simpan ke array bilangan prima yg telah diketahui
        if (nap !== true)
        {
            prime[c] = num; c++;
        }
    }
    return prime;
}

Uji Coba

Silakan gunakan test sederhana berikut untuk mengetahui manakah yang lebih efisien, pencarian bilangan prima menggunakan SOE atau menggunakan cara biasa.





Kesimpulan

Dari percobaan yang kulakukan, cara SOE lebih cepat daripada pencarian biasa. Untuk pencarian hingga range 1000000, cara SOE membutuhkan waktu rata-rata 500 milidetik, sedang pencarian menggunakan cara biasa membutuhkan waktu rata-rata 3 detik. Terima kasih telah membaca, semoga bermanfaat, Happy Coding!!

Referensi:

  • http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
  • http://mkaz.com/math/primes/prime_numbers.html

Hartadi

I’m a Passionate Programmer ;)

One thought to “Mencari Deret Bilangan Prima Menggunakan Algoritma Sieve of Eratosthenes”

Leave a Reply