Eratosten Kalburu

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.

2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20

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.

2 3 5
7 9
11 13 15
17 19

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.

2 3 5
7
11 13
17 19

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.

2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

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.

2 3 5 7 9
11 13 15 17 19
21 23 25 27 29
31 33 35 37 39
41 43 45 47 49

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

2 3 5 7
11 13 17 19
23 25 29
31 35 37
41 43 47 49

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

2 3 5 7
11 13 17 19
23 29
31 37
41 43 47 49

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

2 3 5 7
11 13 17 19
23 29
31 37
41 43 47

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.

You may also like...

Bir yanıt yazın