Cara Mencari Bilangan Prima dengan Saringan Eratosthenes

Definisi dari bilangan prima yaitu bilangan bulat yang hanya mempunyai tepat dua faktor yang berbeda, dengan kata lain hanya bisa habis dibagi oleh tepat dua bilangan yaitu 1 dan bilangan itu sendiri
Jika suatu bilangan yang lebih besar dari satu bukan bilangan prima, maka bilangan itu disebut bilangan komposit. Cara paling sederhana untuk menentukan bilangan prima yang lebih kecil dari bilangan tertentu adalah dengan menggunakan saringan 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. 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 untuk menentukan bilangan prima dengan saringan erastothenes adalah :

1. Coret angka 1
2. Lingkari angka 2 dan coret kelipatannya
3. Lingkari angka 3 dan coret kelipatannya
4. Lingkari angka 5 dan coret kelipatannya
5. Lingkari angka 7 dan coret kelipatannya