Tapis Eratosthenes

Saringan Eratosthenes adalah suatu cara untuk menemukan semua bilangan prima diantara 1 dan suatu angka n. Saringan ini ditemukan oleh Eratosthenes, seorang ilmuwan Yunani kuno.

Langkah-langkah saringan Eratothenes

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.