The Sieve of Eratosthenes : Membuat list bilangan prima

   Ada salah permasalahan yang cukup menarik, yaitu membuat list bilangan prima dari 1 sampai N. Kita bisa saja mengecek satu-persatu bilangan dari 1 (yang pasti bukan prima) sampai N, apakah dia prima atau tidak. Akan tetapi proses ini cukup melelahkan untuk nilai N yang lumayan besar, dan butuh ketelitian (apabila dilakukan manual). Ada sebuah trik yang bisa mempermudah pekerjaan kita. Trik ini disebut The Sieve of Eratosthenes.

   Idenya cukup sederhana : Buat list bilangan dari 1 sampai N, lalu kita akan mencoret bilangan komposit. Pertama, kita coret bilangan 1, karena 1 bukan prima. Lalu kita mulai dari 2. Karena 2 adalah bilangan prima, maka kita lingkari (atau diamkan saja) angka 2, lalu kita coret semua bilangan kelipatan 2. Setelah itu, kita "geser" ke bilangan selanjutnya yang belum kita coret (yaitu 3), lalu lakukan proses yang sama seperti pada angka 2. Proses ini kita lakukan terus sampai mencapai bilangan sqrt(N) (karena N = sqrt(N) x sqrt(N)).

   Setelah itu, kita bisa lihat dari list yang kita miliki, bilangan yang tidak kita coret adalah bilangan prima. Kalau ingin melist bilangan prima saja, ya tinggal buat list baru yang isinya hanya bilangan prima saja.

   Tentunya, hal ini bisa juga diaplikasikan dalam pemrograman. Kita bisa membuat array (sebut saja arr[N]) berisi bilangan dari 1-N, dengan arr[i] = i. Kemudian, kita simulasikan proses mencoret tersebut. Untuk menandai pencoretan bisa menggunakan array boolean atau bitset (pada C++), atau bahkan bitwise(agak tricky sih). Atau untuk mempermudah proses, kita bisa abaikan angka 1, karena angka 1 bukan bilangan prima. Apabila kita ingin membuat list yang hanya berisi bilangan prima saja, kita bisa langsung memasukan nilai yg tidak kita coret (atau yg sedang kita "lingkari") ke dalam array atau vector (array dinamis). Hal ini juga bisa digunakan untuk mencari bilangan prima ke-M dengan prima ke-M <= N. Untuk kompleksitas waktunya, O(N log log N) [2], cukup cepat untuk N yang kisaran jutaan. (tapi soal kompleksitas mungkin juga tergantung pada bagaimana anda mengimplementasikannya. Bahkan, cara yang saya sebutkan tadi bisa dioptimasi lagi untuk menghemat space. Clue : tidak usah buat list bilangan dari 1-N)

   Cukup sekian, semoga bermanfaat.

===========================================================
Update:

Berhubung saya sedang tidak malas, saya membuat implementasi kodenya (beserta isPrime utk mengecek apakah suatu bilangan prima atau tidak) dalam bahasa pascal

Link: Implementasinya

===========================================================
Referensi tambahan :
 [1] https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
 [2]Halim, Steven. 2013. Competitive Programming 3 : The New Lower Bound of Programming Contest. Lulu. Singapore.