Antik dünyanın en pratik matematikçilerinden Eratosthenes, M.Ö. 3. yüzyılda asal sayıları bulmanın o kadar zarif bir yöntemini buldu ki, 2200 yıl sonra hâlâ bilgisayarların temel algoritmalarından biri olarak kullanılıyor. Bu rehberde kalbur yöntemini elle uygulamayı öğrenecek, 100'e kadar olan tüm asal sayıları kendiniz bulacaksınız.
Yöntemin Mantığı
Fikir çok basittir:
- 2'den başlayın; bu bir asaldır.
- 2'nin katlarının üzerini çizin (4, 6, 8, 10...) — bunlar asal olamaz.
- Sıradaki üstü çizilmemiş sayıya geçin (3); bu da asaldır.
- 3'ün katlarının üzerini çizin (9, 15, 21... — 6 zaten çiziliydi).
- Tüm liste bitene kadar devam edin.
Elde kalanlar asal sayılardır. Tıpkı ince gözenekli bir kalburdan irmik ayıklamak gibi!
100'e Kadar Uygulama
1'den 100'e kadar sayıları bir tabloya dizin ve adımları izleyin:
| Adım | Asal | Elenecek Sayılar (katlar) |
|---|---|---|
| 1 | 2 | 4, 6, 8, 10, 12, 14, 16, 18, 20, ... 100 |
| 2 | 3 | 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99 |
| 3 | 5 | 25, 35, 55, 65, 85, 95 |
| 4 | 7 | 49, 77, 91 |
Bir sonraki asal 11'dir; fakat 11² = 121, 100'den büyüktür. 11 ve katları (22, 33, 44...) zaten daha önceki adımlarda elenmiştir. Genel kural: n'e kadar olan sayılarda, √n'den küçük asalların katlarını elemek yeterlidir. √100 = 10 olduğundan 2, 3, 5 ve 7 ile bitirmek kâfidir.
Sonuç listesi: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 — tam 25 asal sayı.
Adım Adım Kontrol Tablosu
İlk 30 sayı için eleme nasıl görünür, inceleyelim (K = kalır/asal, E = elenir):
| Sayı | 2 ile | 3 ile | 5 ile | Sonuç |
|---|---|---|---|---|
| 2 | — | — | — | K (asal) |
| 3 | kurtulur | — | — | K (asal) |
| 4 | E | E | ||
| 5 | kurtulur | kurtulur | — | K (asal) |
| 9 | kurtulur | E | E | |
| 15 | kurtulur | E | E | E |
| 17 | kurtulur | kurtulur | kurtulur | K (asal) |
| 21 | kurtulur | E | E | |
| 25 | kurtulur | kurtulur | E | E |
| 27 | kurtulur | E | E |
Sınıfta Uygulama Etkinliği
Öğretmenler için hazır bir etkinlik:
- Her öğrenciye 1-100 arası sayı kartları verin.
- "2'nin katları" komutunda ilgili öğrenciler otursun.
- "3'ün katları", "5'in katları", "7'nin katları" ile devam edin.
- Ayakta kalan 25 öğrenci asal sayılardır!
- Tartışın: Neden 1 ayakta kaldı ama asal değil? (1 hiçbir adımda elenmez ama asal tanımını sağlamaz.)
Bilgisayarda: Segmenteli Kalbur
Klasik yöntem 10⁶'ya kadar sorunsuzdur; daha büyük aralıklarda ise bellek dostu bir varyant kullanılır: segmenteli kalbur (segmented sieve). Aralık küçük parçalara bölünür ve her parça klasik yöntemle elenir. Sitemizdeki Aralıktaki Asal Sayılar aracı tam olarak bu yöntemle çalışır; böylece "1 milyar ile 1 milyar 10 bin arasındaki asallar" gibi sorgular bile anında yanıtlanır.
function kalbur(n):
liste = [True] * (n+1)
liste[0] = liste[1] = False
for i in 2..sqrt(n):
if liste[i]:
for j in i*i .. n adim i:
liste[j] = False
return [i for i in 0..n if liste[i]]
Yalnızca birkaç satır kod, 2200 yıllık bir fikri çalışır hâle getirir!
Yöntemin Zayıf Yönleri
- Yalnızca listelemek içindir: Tek bir sayının asal olup olmadığını sormak için en iyi yol değildir (o iş için bölme denemeleri veya Miller-Rabin daha uygundur).
- Bellek kullanımı: Klasik sürüm, 10⁹'a kadar tek seferde dizi ayırmak ister; bu yüzden segmenteli sürüm tercih edilir.
Sonuç
Eratosthenes kalburu; asalların katlarını sırayla eleyerek asal sayıları bulan basit, hızlı ve zamansız bir yöntemdir. 100'e kadar elle uygulayarak 25 asal sayıyı kendiniz keşfedebilir, aralık aracımızla herhangi bir aralıkta sonucu doğrulayabilirsiniz.