Saringan Eratosthenes

 Saringan Eratosthenes adalah suatu cara untuk menemukan semua bilangan prima di antara 1 dan suatu angka n. Saringan ini ditemukan oleh Eratosthenes, seorang ilmuwan Yunani kuno. Cara ini merupakan cara paling sederhana dan paling cepat untuk menemukan bilangan prima, sebelum Saringan Atkin
ditemukan pada tahun 2004. Saringan Atkin merupakan cara yang lebih
cepat namun lebih rumit dibandingkan dengan Saringan Eratosthenes.

 

 Langkah-Langkah Saringan Erathostenes

 Misalkan kita hendak menemukan semua bilangan prima di antara 1 sampai suatu bilangan bulat n.

1. Tulis semua bilangan, mulai dari 1 sampai n. Misalkan ini adalah daftar A.


2. Buat suatu daftar yang masih kosong, sebut saja daftar B.


3. Coret bilangan 1 dari daftar A.


4. Lalu tulis 2 pada daftar B. Lalu coret 2 dan semua kelipatannya dari daftar A


5. Bilangan pertama yang belum tercoret dari daftar A (misalnya 3)
   adalah bilangan prima. Tulis bilangan ini di daftar B, lalu coret
   bilangan ini dan semua kelipatannya dari daftar A.


6. Ulangi langkah 4 sampai semua bilangan di daftar A sudah tercoret.

Setelah selesai, semua bilangan di daftar B adalah bilangan prima.

Animasi saringan Eratosthenes dari 1 sampai n=120. Daftar A (kiri) dan daftar B (kanan). Bilangan yang sudah diwarnai artinya sudah dicoret.