Matematiğin ve sayı teorisinin en saf, en gizemli yapı taşları şüphesiz Asal Sayılardır. Yalnızca 1'e ve kendisine kalansız bölünebilen bu sayılar, modern dijital dünyada kredi kartı işlemlerimizi, askeri haberleşmeleri ve kripto para cüzdanlarını koruyan en güvenilir kalkanlardır. Peki bilgisayara 1 ile 1.000.000 arasındaki tüm asal sayıları bulmasını söylediğimizde bunu nasıl yapmalıdır? Her sayıyı kendisinden küçük sayılara tek tek bölmeye kalkarsa işlemci dakikalarca kilitlenir. M.Ö. 200'lü yıllarda İskenderiye Kütüphanesi'nin müdürü olan Yunan bilgini Eratosthenes tarafından geliştirilen Eratosthenes Kalburu (Sieve of Eratosthenes), binlerce yıldır aşılamayan benzersiz bir asal eleme algoritmasıdır.
1. İlkel Yöntem vs Eratosthenes Kalburu
İlkel Yöntem (Brute Force):
Bir sayının ($N$) asal olup olmadığını test etmek için 2'den başlayarak $\sqrt{N}$'e kadar olan sayılara bölersiniz. Eğer hiçbirine bölünmüyorsa asaldır. Bu yöntem tek bir sayıyı test ederken fena değildir; ancak 1'den $N$'e kadar olan tüm asalları bulmak istediğinizde toplam işlem süresi $O(n \sqrt{n})$ olur.
Eratosthenes'in Dahi Fikri:
Eratosthenes sayıları tek tek bölmek yerine "katları eleme" mantığını buldu:
> "Eğer 2 asalsa, 2'nin tüm katları (4, 6, 8, 10...) asal OLAMAZ, hepsinin üstünü çiz! Sonraki açıkta kalan sayı 3'tür; o halde 3'ün tüm katlarının (6, 9, 12, 15...) üstünü çiz!"
Böylece bölme işlemi yapmadan, sadece çarpım tablosu adımlarıyla ilerleyerek asal olmayan tüm bileşik sayıları bir kalburdan un eler gibi süzeriz!
2. Neden Yalnızca $\sqrt{N}$'e Kadar Taramak Yeterlidir?
Bir bileşik sayının çarpanları çiftler halinde gelir: Örneğin 36 için:
$(1, 36), (2, 18), (3, 12), (4, 9), (6, 6)$.
Fark ettiğiniz gibi çarpanlardan biri $\sqrt{36} = 6$'dan küçük veya eşittir. Eğer bir sayının $\sqrt{N}$'e kadar hiçbir asal böleni yoksa, $\sqrt{N}$'den sonra da böleni olması matematiksel olarak imkansızdır! Bu teorem sayesinde kalbur döngümüzü $\sqrt{N}$ değerine ulaştığında güvenle sonlandırabiliriz.
3. Algoritmanın Zaman Karmaşıklığı: $O(n \log \log n)$
Eratosthenes Kalburu'nun işlemci maliyeti, harmonik serilerin asal sayılar üzerindeki toplamıyla hesaplanır:
$$O\left(n \sum_{p \le n} rac{1}{p} ight) = O(n \log \log n)$$
Bu matematiksel karmaşıklık neredeyse doğrusal zamana ($O(n)$) yakındır. 10 Milyon sayı içindeki tüm asalları modern bir dizüstü bilgisayarda sadece 0.5 saniyede eleyebilir!
4. Tam ve Çalışan Python ve C++ Kodları
Python ile Eratosthenes Kalburu:
def eratosthenes_kalburu(n): # Başlangıçta tüm sayıları ASAL kabul eden bir boolean listesi oluştur asal_mi = [True] * (n + 1) asal_mi[0] = asal_mi[1] = False # 0 ve 1 asal değildir p = 2 while p * p <= n: # Eğer p elenmediyse, p bir asaldır! if asal_mi[p]: # p'nin p katından başlayarak tüm katlarını ele (False yap) for i in range(p * p, n + 1, p): asal_mi[i] = False p += 1 # Elenmeyen (True kalan) indeksleri asal sayı listesi olarak topla asallar = [i for i in range(2, n + 1) if asal_mi[i]] return asallar # 100'e kadar olan asalları bul
n = 100
sonuc = eratosthenes_kalburu(n)
print(f"1 ile {n} arasındaki asal sayılar ({len(sonuc)} adet):")
print(sonuc)C++ ile Bellek Optimizasyonlu `std::vector<bool>` Kalburu:
#include <iostream>
#include <vector> void sieve(int n) { std::vector<bool> isPrime(n + 1, true); isPrime[0] = isPrime[1] = false; for (int p = 2; p * p <= n; ++p) { if (isPrime[p]) { for (int i = p * p; i <= n; i += p) { isPrime[i] = false; } } } std::cout << "1'den " << n << "'e kadar olan asallar: "; for (int i = 2; i <= n; ++i) { if (isPrime[i]) std::cout << i << " "; } std::cout << std::endl;
} int main() { sieve(100); return 0;
}5. Kendini Geliştirme Görevi: İkiz Asallar (Twin Primes)
Görev: Aralarındaki fark tam olarak 2 olan asal sayılara İkiz Asal (Twin Primes) denir (Örn: `(3, 5)`, `(5, 7)`, `(11, 13)`, `(17, 19)`). Eratosthenes Kalburu fonksiyonunuzu geliştirerek, verilen bir $N$ sınırına kadar olan tüm ikiz asal çiftlerini listeleyen bir fonksiyon yazın!
6. Parçalı (Segmented) Eratosthenes Kalburu ile Bellek Tasarrufu
Standart kalbur algoritması $N = 10^9$ gibi çok büyük sayılarda gigabaytlarca RAM gerektirir ve bilgisayar belleği yetmeyebilir. Bu sorunu çözmek için Parçalı Kalbur (Segmented Sieve) yöntemi geliştirilmiştir:
7. Goldbach Hipotezi ve Çözülmemiş Asal Gizemleri
1742 yılında Christian Goldbach tarafından ortaya atılan ve yüzyıllardır ispatlanamayan ünlü hipotez şudur:
> "2'den büyük her çift tamsayı, iki asal sayının toplamı şeklinde yazılabilir." (Örn: $4 = 2+2$, $10 = 3+7$, $28 = 5+23$).
Bilgisayarlar ve optimize edilmiş Eratosthenes kalburları kullanılarak bu kural günümüzde $4 imes 10^{18}$ sayısına kadar test edilmiş ve hepsinde doğru çıkmıştır; ancak genel matematiksel ispatı halen dünyanın en büyük ödüllü gizemlerinden biridir.
Sonuç
Eratosthenes Kalburu, antik çağlardan günümüze ulaşan en büyük matematiksel zaferlerden biridir. Kriptografiden sayı teorisine kadar bilgisayar bilimlerinin her köşesinde yaşamaya devam eden bu zarif algoritma, gereksiz hesaplamaları önceden eleme felsefesinin en büyük temsilcisidir. Daha fazla algoritma ve donanım eğitimi için sitemizdeki [Dersler](/dersler) sekmesini takip edin!