Eratosten Kalburu

Eratosten Kalburu Şimdi size, bir N limitine kadarki asal sayıları bulmanın antik bir yöntemini anlatacağım. Buna "Eratosten Kalburu" deniyor. Eratosten, milattan önce 276 yılında doğdu. Yani bu yöntem 2000 yıldan daha eski. Ama o kadar basit ve şık ki, bir çocuğa bile kolayca öğretilebilir. Şimdi, diyelim ki, 100'e kadar olan tüm asal sayıları bulmak istiyoruz. Bu limit 1000 de olabilir, 1 milyon da. Yöntem aynı. Buradaki hiçbir sayı işaretlenmemiş. Yani kutu griyse, işaretsiz demektir. En baştan başlayarak sırayla ilerleyeceğiz. İşaretsiz gördüğümüz tüm sayılara asal diyeceğiz. Karşımıza ilk çıkan sayı, 2 oldu. Demek ki 2 asalmış. Çünkü işaretli değil. İkinci aşamada, 2'nin tüm katlarını eliyoruz. Çünkü hepsinin bileşik olduğunu biliyoruz. Güm! 2'nin katlarını eleyerek büyük bir sıçrama yaptık. Bu arada kırmızıyla işaretlenen sayılar, bileşik sayılar. Şimdi aynısını tekrar ediyoruz. 2'den 3'e geçtik. 3 de işaretsiz. O halde 3 de asaldır, diyoruz. Ve 3'ün tüm katlarını eliyoruz. Burada basit bir püf noktası var. 6'nın zaten elendiğini görüyorsunuz. Dolayısıyla elemeye asal sayının karesinden başlayabiliriz. 3 kere 3, 9. 9'dan başlayarak 3'ün tüm katlarını bileşik sayı olarak işaretleyebiliyoruz. 4'e geçiyoruz. 4 işaretli. Demek ki bileşik bir sayı. 5'e atlıyoruz. İşaretsiz olduğuna göre 5, asal bir sayıdır. 5 kere 5, 25. 25'ten başlayıp 25, 30, 35, 40, 45... Hepsini işaretliyoruz. Çünkü hepsi bileşik. 6'yı atladık, 7'ye geldik. İşaretli olmadığına göre 7 asal. 7 kere 7, 49. 49'dan başlayarak 7'nin tüm katlarını bileşik sayı olarak işaretliyoruz. Devam ediyoruz. Bunları atlayıp 11'e geldik. 11 de asal bir sayı. Dikkat edin, 11 çarpı 11, 100'den büyük bir sayı. Dolayısıyla bu noktada artık durabiliriz. 10'da bile dursak olurdu. İşte, geri kalan tüm işaretsiz sayılar asal sayılar. Bir hamlede hepsini asal olarak işaretliyoruz. Tüm algoritma bundan ibaret. Çok basit. Bu kalbur hesabını yapacak bir program yazmak için algoritmayı genişletmemiz gerekirse, Bir N sayısına kadar olan tüm asal sayıları bulmak için, Bir "for" döngüsü oluşturuyoruz. Türkçe olarak düşünürsek "için", yani 2'den karekök n'e kadar olan tüm a sayıları için. Dikkatinizi çekerim, biz de burada 10'a kadar geldiğimizde durmuştuk. Gerçi ben 11'e kadar gelmiştim ama. Yani 2'den karekök n'e kadarki tüm sayılar için şunları tekrarlıyoruz: Eğer yani IF (if) komutunu koyuyoruz, a işaretsizse, o halde yani THEN (den), a asal sayıdır. a'nın tüm katlarını bileşik sayı olarak işaretliyoruz. İşte bu kadar. Asal sayıyı bul, katlarını işaretle; en başa dön, a'yı 1 arttır. Yani bir önceki sayı 2'yse şimdi 3'e geç. Sonra 4, sonra 5, böyle devam et. İşlem tamamlandığında, tüm asalları bulmuş oluyoruz. Bunun da bir döngü olduğuna dikkatinizi çekerim. Bir ana "for" döngümüz var. Bu döngü içinde bir asal bulursak, onun katlarını yine bir döngüyle işaretliyoruz. Bunu görebilmek önemli. Burada iç içe döngüler söz konusu. Yani bir döngünün içinde başka bir döngü var. Bu algoritmanın çalışır bir örneğini göstereyim. Aşağıya bir javascript(cavaskript) yazmıştım. Eğer 100 değerini girersem, verdiği tüm asallar 100'den küçük oluyor. 200 girersem, 200'den küçük asalları veriyor. 850 girersem. İşte, 850'den küçük tüm asal sayılar. Videonun altındaki linkten, bu script'e ve kodu nasıl yazdığımı anlatan orjinal videoya ulaşabilirsiniz. Hoşçakalın!