Eratosthenes Kalburu ile Asal Sayı Bulma
Bir sayının asal olup olmadığını tek tek test etmek yerine, belirli bir aralıktaki tüm asalları aynı anda bulmak istediğinizde en pratik yöntem MÖ 3. yüzyıldan kalma Eratosthenes Kalburu'dur. Bu rehberde algoritmayı, 1-50 aralığının gerçek adım adım eleme tablosuyla baştan sona uyguluyoruz.
Eratosthenes Kalburu nedir?
"Kalbur" benzetmesi tam yerinde: undan kepeği ayıklar gibi, sayı listesinden bileşikleri eleyip geriye yalnızca asalları bırakırsınız. Aşağıda bu eleme işlemini 1'den 50'ye kadar gerçek adımlarla uyguluyoruz; büyük aralıklarda aynı mantığı hesaplayıcının aralık tarama modu otomatik yapar.
Kısa tarihçe
Eratosthenes, MÖ 3. yüzyılda yaşamış, aynı zamanda Dünya'nın çevresini şaşırtıcı bir doğrulukla hesaplamasıyla da tanınan bir Yunan matematikçi ve coğrafyacıydı. Kendi adını taşıyan bu algoritma, o dönemden beri kullanılmasına rağmen hâlâ belirli aralıklardaki asalları bulmanın en verimli klasik yöntemlerinden biridir; modern bilgisayarlarda da küçük optimizasyonlarla (segmentli kalbur gibi) aynen kullanılır.
Algoritma nasıl çalışır?
Algoritmanın mantığı beş basit adıma indirgenebilir:
- Liste oluştur: 2'den n'e kadar tüm sayıları yaz; hepsini başlangıçta "asal adayı" say.
- En küçük işaretsiz sayıyı seç: İlk adımda bu her zaman 2'dir; 2'yi asal ilan et.
- Katlarını ele: Seçilen asalın kendisi hariç tüm katlarını (4, 6, 8, 10… veya 9, 12, 15…) listeden ele.
- Sıradaki işaretsiz sayıya geç: Elenen sayılar hariç, listede işaretlenmemiş bir sonraki sayıyı yeni asal ilan et ve 3. adımı tekrarla.
- Karekök sınırına ulaşınca dur: Denenen asalın karesi n'yi geçtiğinde işlem biter; elenmeden kalan tüm sayılar asaldır.
Adım adım örnek: 1-50 aralığı
1'den 50'ye kadar olan sayılarda Eratosthenes Kalburu'nu gerçek adımlarla uygulayalım. Üst sınırımız 50 olduğu için, karekökü (√50 ≈ 7,07) geçmeyen asallarla — yani yalnızca 2, 3, 5 ve 7 ile — eleme yapmamız yeterlidir.
| Adım | Eleme yapan asal | Yeni elenen sayılar | Elenen adet |
|---|---|---|---|
| 1 | 2 | 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50 | 24 |
| 2 | 3 | 9, 15, 21, 27, 33, 39, 45 | 7 |
| 3 | 5 | 25, 35 | 2 |
| 4 | 7 (7² = 49 ≤ 50, dur) | 49 | 1 |
Toplam elenen sayı: 24 + 7 + 2 + 1 = 34. Geriye 2'den 50'ye kadar 49 sayıdan 34'ü elendiği için 15 sayı asal olarak kalır.
Dikkat edin: 2. adımda 3'ün katlarından yalnızca tek olanlarını (9, 15, 21…) yeni eleniyor gösterdik, çünkü 6, 12, 18, 24, 30, 36, 42, 48 gibi çift katlar zaten 1. adımda (2'nin katları olarak) elenmişti. Aynı şekilde 3. adımda 5'in katlarından yalnızca 25 ve 35 "yeni" elenendir; 10, 15, 20, 30, 40, 45, 50 zaten önceki adımlarda elenmişti. Bu tekrar eleme yapmama özelliği, algoritmayı deneme bölmesinden çok daha hızlı yapan şeydir.
1-50'yi ya da istediğin aralığı anında tara
Hesaplayıcı, girdiğiniz aralıktaki tüm asal sayıları Eratosthenes Kalburu ile saniyeler içinde listeler (2.000.000'a kadar).
1-50 Aralığını Tara →Neden 7'de duruyoruz? (karekök sınırı)
Bunun mantığı basittir: eğer bir sayı n'nin (burada 50) altında bileşikse, en az iki bölene ayrılabilir ve bu bölenlerden en az biri √n'den küçük veya eşit olmalıdır (ikisi de √n'den büyük olsaydı çarpımları n'yi aşardı). Bu yüzden √n'e kadar olan asallarla eleme yapmak, aralıktaki tüm bileşikleri yakalamak için yeterlidir.
Sonuç: 1-50 arası asal sayılar
Eleme tamamlandığında geriye kalan (elenmemiş) sayılar 1-50 aralığındaki tüm asal sayılardır — toplam 15 asal:
Vurgulu (koyu) sayılar asaldır: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Aynı yöntemi 100'e kadar genişletirsek — yani ek olarak 11 (11² = 121 > 100 olduğu için aslında 7'den sonra ek eleme gerekmez, 100 için de son eleyici asal 7'dir) — 25 asal sayı elde edilir. Tam listeyi ve daha büyük aralıkları hesaplayıcının aralık tarama modunda görebilirsiniz.
Eratosthenes Kalburu ile deneme bölmesi karşılaştırması
Tek bir sayının asal olup olmadığını test etmek için deneme bölmesi yeterlidir, ama bir aralıktaki tüm sayıları tek tek deneme bölmesiyle test etmek çok daha yavaştır — çünkü her sayı için işlem baştan başlar. Eratosthenes Kalburu ise bir eleme yaptıktan sonra bu bilgiyi tüm katlar için yeniden kullanır.
| Özellik | Eratosthenes Kalburu | Deneme bölmesi (tek tek) |
|---|---|---|
| Amaç | Aralıktaki tüm asalları bulma | Tek bir sayıyı test etme |
| Karmaşıklık | ~O(n log log n) | ~O(n√n) (aralık için) |
| 1-1.000.000 aralığında | Saniyenin çok altında | Belirgin şekilde yavaş |
| Bellek kullanımı | n boyutunda dizi gerekir | Sabit (ekstra bellek gerekmez) |
Kaynak: standart algoritma karmaşıklığı analizi; BirAraçta motoru aralık taramada Eratosthenes Kalburu'nu, tekil sayı testinde deneme bölmesi/Miller-Rabin'i kullanır.
Eratosthenes Kalburu ne zaman kullanılır?
- Bir aralıktaki tüm asalları listelemek gerektiğinde (ör. "1-1000 arası asal sayılar hangileri?").
- Asal sayı sayımı yapılırken (ör. "100'e kadar kaç asal var?").
- Ön hesaplama (ön bellekleme) gerektiren uygulamalarda; bir kez hesaplanan asal listesi tekrar tekrar kullanılabilir.
- Eğitimde, asal sayı kavramını görsel ve elle uygulanabilir biçimde öğretmek için idealdir.
Buna karşılık tek, çok büyük bir sayının (ör. 18 haneli bir sayının) asal olup olmadığını test etmek istiyorsanız kalbur pratik değildir — bu durumda Miller-Rabin gibi doğrudan asallık testleri çok daha hızlı sonuç verir.