BÖLÜM 2: ERATOSTHENES KALBURU

Erathosthenes kalburu belirli bir sayıdan küçük asal sayıları bulabilmek için kullandığımız bir eleme yöntemidir. Bu yöntemde 2’den başlayarak belirlediğimiz sayıya kadar olan tüm doğal sayıları listeleriz. Listedeki sayıları en küçükten başlayarak sırayla ele alırız. Elemediğimiz sıradaki en küçük sayıyı asal olarak işaretleriz. Bir asal sayının kendisinden farklı tam katları asal olamayacağı için bu asal sayının katlarının tümünü listeden eleriz.

Listede tam katı olmayan bir asal sayı bulana kadar eleme işlemlerine devam ederiz. Böyle bir asal sayı ile karşılaştığımızda ise listede kalan tüm sayıları asal olarak işaretleriz.

Yukarıda 2’den 100’e kadar olan asal sayıları buluyoruz. Bunun için sırayla,

2’den 100’e kadar olan sayıları listeliyoruz.
Listedeki en küçük sayı olan 2’yi asal olarak işaretliyoruz.
2’nin kendisinden farklı olan tam katlarını (4, 6, 8, 10, …) listeden eliyoruz.
Listede geriye kalan en küçük sayı 3 olduğu için 3’ü asal olarak işaretliyoruz.
3’ün tam katlarını (6, 9, 12, 15….) listeden eliyoruz. Çift katlar (6, 12, 18,…) daha önce elendiği için bu sayılarla ilgili bir işlem yapmıyoruz.
Listedeki en küçük sayı olan 5’i asal olarak işaretliyoruz.
5’in kendinden büyük tam katlarını eliyoruz.
Geriye kalan en küçük sayı 7 olduğu için 7’yi de asal olarak işaretliyoruz.
7’nin tam katlarını da listeden çıkarıyoruz.
Geriye kalan sayılardan en küçüğü 11’dir. Bu sayıyı da asal olarak işaretliyoruz.
Listede 11’in tam katı kalmadığı için geriye kalan sayıların tümünü asal olarak işaretliyoruz.