Sieve of Eratosthenes

Türkçesi eratosthenes elemesi anlamına gelen Sieve Of Eratosthenes, 2'den başlayarak istenilen limite (örn: 30) kadar olan asal sayıları bulmamızı sağlar. Basit bir örnekle anlatmak gerekirse;

25 sayısına kadar olan asal sayıları bulmak istediğimizi düşünelim. 

Sayı dizimiz bu şekilde olur: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Adım 1: Sayı dizisinde 2'nin katlarını seçer ve sayı dizisinden çıkarırız. Buna göre yeni dizimiz.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25    (Kalın fontlar elenen sayıları temsil ediyor.)

Adım 2: Sayı dizisinden üstü çizilmemiş olan 3'ün katlarını seçer ve sayı dizisinden çıkarırız. Buna göre yeni dizimiz.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Adım 3: Sayı dizisinden 4'ün katlarını çıkarmıyoruz çünkü 2'nin katı olan 4'ü zaten sayı dizisinden çıkardık.

Adım 4 : Üstü çizilmemiş olan 5'in katlarını sayı dizisinden çıkarıyoruz. Buna göre yeni dizimiz.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Adım 4: Üstü çizilmiş olan 6 ve katlarını çıkarmıyoruz. Çizilmemiş olan 7'in katlarını sayı dizisinden çıkartabiliriz fakat hali hazırda 7'nin tüm katlarını diziden çıkardık (14 21). Dikkat ederseniz, 11'in katlarını da zaten elemiş olduk. Eğer 13'ün katlarını almaya çalışırsak dizimizin boyutunu aşarız bu yüzden almıyoruz. Şimdi elimizdeki diziden elediğimiz sayıları çıkartalım. Buna göre dizimiz;

2 3 5 7 11 13 17 19 23 şeklinde olur. Geriye sadece asal sayıların kaldığına dikkat edin. Eğer 100' e kadar olan sayıların içindeki asal sayıları bulmak isteseydik o zaman 7, 11 ve 13 sayılarının katlarını da diziden çıkarmamız gerekecekti.