Sieve of Eratosthenes – Metode untuk Mengidentifikasi Bilangan Prima

Dalam kompetisi informatika, seperti Olimpiade Komputer di Indonesia, kasus problem solving yang melibatkan bilangan prima sering muncul, dari yang sederhana, hingga kasus yang kompleks. Tulisan ini membahas algoritma Sieve of Eratosthenes untuk mengidentifikasi bilangan prima, yang nantinya dapat diimplementasikan untuk kasus problem solving yang lebih kompleks. Untuk hal itu, saya akan mengimplementasikan algoritma ini dalam bahasa Pascal dan C.

Ini adalah kutipan wikipedia.org untuk algoritma Sieve of Erathosthenes (lihat http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)

A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself.
To find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

  1. Create a list of consecutive integers from two to n: (2, 3, 4, …, n).
  2. Initially, let p equal 2, the first prime number.
  3. Strike from the list all multiples of p less than or equal to n. (2p, 3p, 4p, etc.)
  4. Find the first number remaining on the list after p (this number is the next prime); replace p with this number.
  5. Repeat steps 3 and 4 until p2 is greater than n.
  6. All the remaining numbers in the list are prime.

Oke, mari kita langsung ke implementasi program dalam bahasa Pascal (saya merekomendasikan Anda untuk men-download Free Pascal dari http://www.freepascal.org/ yang saat saya menggunakannya, sudah memasuki versi 2.4)

const
    N = 1024;

Pertama, kita siapkan dulu larik (array) 1 dimensi. Untuk kasus ini, saya hanya memberikan contoh untuk bilangan prima dalam rentang 1..1024.

var sieve: array[1..N] of integer;

Siapkan juga 2 buah variabel untuk iterator

    i, p : integer;

Nah, kita mulai implementasinya. Pertama, kita ikuti langkah yang didefinisikan di atas. Siapkan isi variabel p dengan 2, kemudian siapkan variabel n yang menampung nilai 2, 3, 4, …, n. Dalam kasus ini, saya akan menggunakan variabel i sebagai penggantinya.

begin
    p := 2;

Langkah ke-3, kita hilangkan semua hasil kali p dengan setiap nilai i. Dalam kasus ini, saya batasi N = 1024, yang berarti i = {2, 3, …, 1024)

    while (p * p <= N) do begin
        i := 2;

        while (p * i <= N) do begin
            sieve[p * i] := -1;
            inc(i);
        end;

Langkah ke-4, isikan nilai p dengan angka prima selanjutnya, implementasinya:

        inc(p);
        while (sieve[p] = -1) do
            inc(p);
    end;

Untuk tambahan, karena dalam operasi larik (array) ini kita tidak menyenggol bilangan ke-1 (ingat bahwa 1 bukan bilangan prima) sekalipun, tambahkan kode ini untuk melengkapi.

    sieve[1] := -1;

Nah, secara otomatis, karena kita sudah menggunakan blok while, langkah ke 5 dan 6 telah ter-cover dengan baik. Jadi, apa hasil yang kita dapatkan? Kita memiliki suatu array bernama sieve, yang telah disaring, sedemikian sehingga jika suatu elemen (misalnya elemen ke-i) adalah bilangan prima, maka nilai dari elemen ke-i tersebut adalah 0. Jika bukan merupakan bilangan prima, maka isi elemen tersebut adalah -1. Untuk menguji, kita bisa tampilkan seluruh bilangan prima yang telah tertampung di dalam larik (array) tersebut.

    for i := 1 to N do
        if (sieve[i] = 0) then writeln(i);

Dengan demikian, selesailah teknik Sieve of Eratosthenes. Implementasi dari algoritma di atas dapat diterapkan untuk pemecahan masalah pemrograman yang lain.

Ini salinan program lengkapnya dalam Bahasa Pascal.

const
    N = 1024;

var
    sieve : array[1..N] of integer;
    i, p  : integer;

begin
    p := 2;

    while (p * p <= N) do begin
        i := 2;

        while (p * i <= N) do begin
            sieve[p * i] := -1;
            inc(i);
        end;

        inc(p);
        while (sieve[p] = -1) do
            inc(p);
    end;

    for i := 1 to N do
        if (sieve[i] = 0) then writeln(i);

end.

Untuk bahasa C, berikut implementasinya (mohon diperhatikan, karena implementasi array dalam bahasa C, indeks pertama dimulai dari 0, bukan dari 1 seperti pada bahasa Pascal)

#include <stdio.h>

const int N = 1024;

int main() {
    int sieve[1024] = {0};

    int p = 2;

    while (p * p <= N) {
        int i = 2;

        while (p * i <= N) {
            sieve[p * i -1] = -1;
            i++;
        }

        p++;
        while (sieve[p-1] == -1) {
            p++;
        }
    }

    sieve[0] = -1;

    int i;

    for (i = 0; i < N; i++) {
        if (sieve[i] == 0)
            printf("%i\n", i+1);
    }

    return 0;
}

Semoga bermanfaat.

Catatan:
Karena saya masih pemula, barangkali, kode-kode di atas ada yang salah. Mohon segera comment artikel ini jika ada yang keliru agar saya bisa memperbaikinya. Kontribusi Anda akan sangat membantu. Terima kasih.

Penulis bisa ditanya-tanyai di imam.hidayat92@gmail.com

2 comments

  1. illie · October 25, 2010

    inii uda membantu kok,, ada tugas tentang sieve ini,, tapi ga tau maksudnya,, thanks berat,..

  2. Imam Hidayat · October 26, 2010

    Sama-sama. Senang bisa membantu🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s