Eratosten Kalburu

15 Nisan 2011 0 Yazar: İbrahim AY
1 Star2 Stars3 Stars4 Stars5 Stars (Oy verilmemiş. İlk oy veren olur musun?)
Loading...

Eratosten kalburu, belirlediğimiz bir sayıya kadar ki asalları belirlemek için kullanılan sayısal bir yöntemdir. Uygulamanın anlaşılabilir olması için kısa bir örnek ile başlayalım ve 20’ye kadar ki asal sayıları belirleyelim.

1 asal olmadığı için 2’den başlayak 20’ye kadar ki sayıları yazıyoruz.

2345
678910
1112131415
1617181920

2 asal sayılar içinde çift olan tek asal sayıdır. Zira sadece 1’e ve kendine bölünebilir. 2’nin katları asal olamazlar çünkü 2’ye bölünebilirler. Öyle ise 2’nin katları olan 4, 6, 8, 10, 12, 14, 16, 18 ve 20’yi tablodan silelim.

235
79
111315
1719

2’den sonraki ilk sayı asaldır. Yani 3 asaldır. 3’ün katları ise asal değildir. O zaman 9 ve 15’i tablodan silelim.

235
7
1113
1719

3’ten sonraki ilk sayı asaldır. Yani 5 asaldır. Daha önce yaptığımız gibi 5’in katlarını silelim diyeceğim ama kalmadı. Bu noktadan ötede silinebilecek bir değer bulunmaz. Neden? Tablomuz 20’ye kadardı. 5’in karesi 25’tir ve 20’den büyüktür. Daha sonraki değerlerin katları da doğal olarak tabloda bulunamaz. Kendinden önceki sayıların katlarını zaten silmiştik. Öyle ise 2’den 20’ye kadar ki asal sayılar 2, 3, 5, 7, 11, 13, 17 ve 19’dur.

Görüldüğü gibi silme işlemini tablomuzda ki en büyük sayının kareköküne kadar sürdürmek yeterlidir (tam sayı olarak karekökü yoksa tamsayı kısmına kadar). 20’nin kökü 4,17 olduğuna göre işlemi 4’ten sonra sürdüremeyiz zira ötedeki sayıların katları tabloda yoktur. (7, 11, 13, 17 ve 19’un katları tabloda yoktur. Öyle ise bu sayılar asaldır).

Örneğimizi büyültelim ve 50’ye kadar ki asallara bakalım.

2345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950

Silme işlemini kaça kadar yapacağız.
50’nin kare kökü 7,07 olduğuna göre işlemlerimizi 7’ye kadar sürdürdükten sonra silinecek sayı kalmaz. 50’nin karekökü tamsayı değildir ve karesi 50’den küçük en yakın tamsayı 7’dir (7*7=49). Buradan da yola çıkarak 7’de işlem biter diyebiliriz.

2 asaldır, katları değildir. 2’nin katlarını silelim.

23579
1113151719
2123252729
3133353739
4143454749

2’den sonraki ilk sayı 3. 3 asaldır, katları değildir.

2357
11131719
232529
313537
41434749

3’ten sonraki ilk sayı 5’tir. Öyle ise 5 asaldır, katları değildir.

2357
11131719
2329
3137
41434749

5’ten sonraki ilk sayı 7. 7 asaldır, katları değildir.

2357
11131719
2329
3137
414347

7’den sonraki sayılarda asaldır. Tablomuzda 50’den büyük sayı yoktur ve 7’den sonra ki sayıların katları tabloda yoktur.

İşlemimiz bitmiştir. Tabloda kalan sayılar asaldır. (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47)

Not: 5 ve sonra ki bütün asal sayılar, 6’nın katlarından 1 fazla veya 1 eksiktirler. Örneğin 13, 6’nın 2 katı olan 12’den bir fazladır veya başka bir örnek olarak 47, 6’nın 8 katı olan 48’den 1 eksiktir. Ancak dikkat ediniz, her x6-1 veya her x6+1 asal sayı değildir.

Konuyu, aşağıda bulunan ve Meyer tarafından yazılmış java uygulaması ile pekiştirebilirsiniz. Önce 2’yi tıklayın katları silinsin, sonra 3’ü, vs. vs.