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 :