Eratosthenes Kalburu: C++ ile Asal Sayıları Bulmanın Temel Yöntemleri

Eratosthenes Kalburu nedir ve nasıl çalışır? Bu yazıda C++ implementasyonlarıyla basit, odd, wheel ve segmentli sieve yöntemleriyle asal sayıları adım adım bulmayı öğreniyoruz.

Posted Aug 23, 2025 Updated Aug 23, 2025

By fr0stb1rd

views 20 min read

Eratosthenes Kalburu: C++ ile Asal Sayıları Bulmanın Temel Yöntemleri

Asal sayılar, tüm tam sayıların yapı taşlarıdır. Hem basitlikleri hem de dağılımlarının tahmin edilemez olmasıyla büyüleyicidirler. Asal sayıları bulmak, özellikle de büyük sayılar söz konusu olduğunda, yüzyıllardır matematiğin temel problemlerinden biri olmuştur. Bu soruna getirilen en eski ve en zarif çözümlerden biri, zamanın süzgecinden geçmiş Eratosthenes Kalburu‘dur.

Bu yöntem, adını Yunan matematikçi Kyreneli Eratosthenes’ten (MÖ 276-195) alır ve her bir sayının asal olup olmadığını tek tek test etmeye dayanmaz. Bunun yerine asal olmayan tüm sayıları sistematik olarak elemek üzerine kurulmuştur.

⚙️ Nasıl Çalışır?

Diyelim ki 30’a kadar olan asal sayıları bulmak istiyorsunuz:

Önce, 2’den başlayarak 30’a kadar olan tüm sayıları bir listeye yazın:
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
Şimdi listeye bakın. İlk sayı olan 2 bizim ilk asalımız. Hadi 2’nin katlarını (4, 6, 8, …, 30) çizelim.
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
Çizilmemiş sıradaki sayı 3. Bu da asal! Şimdi 3’ün katlarını (9, 12, 15, 18, …, 30) eliyoruz.
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
Şimdi sıradaki asalımız 5. Ama dikkat: 5’in katlarını 25’ten (5²) başlayarak elemek yeterli. Çünkü 25’ten küçük olan katlar zaten 2 veya 3 tarafından elenmişti.
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
Sıradaki sayı 7 ama 7² = 49, bizim sınırımız olan 30’dan büyük. Yani artık durabiliriz.

Kalan sayılar asallardır: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

💪 Neden Bu Kadar Güçlü?

Eratosthenes Kalburu’nun güzelliği, bir sayının asal olup olmadığını kontrol etmek için bölme işlemi kullanmamasıdır. Sadece toplama ve işaretleme ile çalışır. Bu da bilgisayarlar için inanılmaz hızlı bir yöntemdir.

Ama iş burada bitmiyor. Günümüzde daha büyük aralıklar için farklı geliştirilmiş sürümler kullanılıyor:

Segmentli Kalbur (Segmented Sieve): Diyelim ki 1 milyardan 1 milyar 1000’e kadar olan asalları bulmak istiyorsunuz. Tüm 1 milyara kadar olan sayıları belleğe sığdırmak mümkün değil. İşte segmentli kalbur devreye giriyor: Aralığı küçük parçalara (segmentlere) ayırıyor ve her parçayı sırayla kalburdan geçiriyor. Böylece bellek kullanımı çok azalıyor.
Çark Kalburu (Wheel Sieve): Asal olmayan bazı sayıların zaten otomatik olarak eleneceğini bildiğimiz durumlarda (örneğin, tüm çift sayılar), eleme işlemi hızlandırılır.
Paralel ve GPU destekli kalburlar: Modern donanımlarda asal sayıları hesaplamak için aynı anda birçok çekirdeği ya da GPU’yu kullanan yöntemler vardır.

🧮 Basit Sieve - Temel Eratosthenes Kalburu

  
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> sieve_simple(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (is_prime[p]) {
            for (int i = p * p; i <= n; i += p)
                is_prime[i] = false;
        }
    }
    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) primes.push_back(i);
    return primes;
}

int main() {
    int n = 30;
    auto primes = sieve_simple(n);
    for (int p : primes) cout << p << " ";
    cout << "\n";
}

📦 Başlık Dosyalarının Dahil Edilmesi

<vector> -> Dinamik boyutlu dizi (vector) yapısı. Burada asal sayıları tutmak için kullanıyoruz.
<cmath> -> Matematiksel işlemler, özellikle karekök (sqrt) için.

🛠️ sieve_simple

  
vector<int> sieve_simple(int n)

n -> Bulmak istediğimiz asal sayıların üst sınırı.
Fonksiyon vector<int> döndürüyor; yani asal sayıların listesini bir vektör olarak veriyor.

🏷️ Asallık işaretleme dizisi

  
vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;

is_prime[i] -> i sayısının asal olup olmadığını tutar.
Başta tüm sayılar asal kabul ediliyor (true).
0 ve 1 asal olmadığından, false olarak işaretleniyor.

🔄 Asal sayı eleme döngüsü

  
for (int p = 2; p * p <= n; p++) {
    if (is_prime[p]) {
        for (int i = p * p; i <= n; i += p)
            is_prime[i] = false;
    }
}

Dış döngü: p = 2‘den başlar ve p * p <= n koşulu ile devam eder.
- Sadece √n kadar gitmek yeterlidir. Çünkü bir sayının küçük bir böleni varsa, büyük böleni zaten önceki adımlarda işaretlenmiş olur.
İç döngü: p asal ise, p*p‘den başlayarak tüm katlarını (p*p, p*(p+1), ...) işaretleriz.
- i += p -> Katları adım adım geçmek için.
- false olarak işaretleme -> artık bu sayı asal değil.

📋 Asal sayıları toplama

  
vector<int> primes;
for (int i = 2; i <= n; i++)
    if (is_prime[i]) primes.push_back(i);

İşaretleme tamamlandıktan sonra, is_prime[i] == true olan tüm sayılar asal olarak kabul edilir.
Bu sayılar primes vektörüne eklenir.

▶️ main

  
int main() {
    int n = 30;
    auto primes = sieve_simple(n);
    for (int p : primes) cout << p << " ";
    cout << "\n";
}

n = 30 -> 30’a kadar olan asal sayıları bulmak istiyoruz.
auto primes = sieve_simple(n); -> Fonksiyonu çağırıyoruz ve sonucu primes vektörüne alıyoruz.
Döngü ile asal sayıları ekrana yazdırıyoruz:
- for (int p : primes) -> Vektördeki her p için çalışır.
- cout << p << " "; -> Asalları yazdırır.

🧩 Algoritma

0 ve 1 asal değil -> işaretle.
2’den √n’ye kadar olan sayılar için:
- Eğer sayı asal ise -> katlarını işaretle (asal değil).
İşaretlenmemiş sayılar -> asal.
Tüm asal sayıları listeye ekle ve ekrana yazdır.

Zaman Karmaşıklığı: O(n log log n)
Bellek Karmaşıklığı: O(n)

💻 Çalıştıralım

  
[fr0stb1rd@archlinux Desktop]$ mkdir demo && cd demo
[fr0stb1rd@archlinux demo]$ nano sieve_simple.cpp
[fr0stb1rd@archlinux demo]$ g++ -o sieve_simple sieve_simple.cpp -O2
[fr0stb1rd@archlinux demo]$ ./sieve_simple 
2 3 5 7 11 13 17 19 23 29 
[fr0stb1rd@archlinux demo]$ 

🥇 Tek Sayılarla Optimize Edilmiş Sieve

  
#include <iostream>
#include <vector>

using namespace std;

vector<int> sieve_odd(int n) {
    if (n < 2) return {};
    int m = (n - 1) / 2;
    vector<bool> is_prime(m + 1, true);
    for (int i = 1; 2 * i + 1 <= n / (2 * i + 1); i++) {
        if (is_prime[i]) {
            int p = 2 * i + 1;
            for (int j = (p * p - 1) / 2; j <= m; j += p)
                is_prime[j] = false;
        }
    }
    vector<int> primes = {2};
    for (int i = 1; i <= m; i++)
        if (is_prime[i]) primes.push_back(2 * i + 1);
    return primes;
}

int main() {
    int n = 30;
    auto primes = sieve_odd(n);
    for (int p : primes) cout << p << " ";
    cout << "\n";
}

🧠 Tek sayıları kullanma mantığı

vector<bool> is_prime(m + 1) -> artık 2 dışındaki tüm sayılar tek sayılar üzerinden tutuluyor.
Bellek tasarrufu sağlıyor, çünkü çift sayılar zaten asal olamaz ve vektörde yer kaplamıyor.
🔢 İndeksleme ve sayılar

  
int m = (n - 1) / 2;

i -> vektördeki indeks.
Sayı = 2*i + 1
Örnek: i=1 -> 3, i=2 -> 5, i=3 -> 7 …

🔁 Dış döngü (√n optimizasyonu)

  
for (int i = 1; 2 * i + 1 <= n / (2 * i + 1); i++)

Sadece 2*i + 1 <= √n kadar gidiyoruz.
Eski sürümle aynı optimizasyon, ancak tek sayılar için indeksleme yapıyoruz.

✖️ Katları işaretleme

  
int p = 2 * i + 1;
for (int j = (p * p - 1) / 2; j <= m; j += p)
    is_prime[j] = false;

p*p’den başlıyoruz (diğer katlar zaten önceki adımlarda işaretlenmiş).
(p*p - 1)/2 -> vektördeki doğru indeks.
j += p -> yalnızca tek sayılar arasında ilerliyoruz.

✍️ 2’yi manuel ekleme

  
vector<int> primes = {2};

2, tek sayı optimizasyonu nedeniyle vektörde yer almıyor -> manuel olarak ekleniyor.

🏗️ Asal sayıları oluşturma

  
for (int i = 1; i <= m; i++)
    if (is_prime[i]) primes.push_back(2 * i + 1);

İşaretlenmemiş her i -> 2*i + 1 sayısı asal.
Bu sayılar vektöre eklenir.

🧩 Algoritma

Tek sayı optimizasyonu sayesinde bellek ~2× azalır.
Algoritma mantığı tamamen aynı; tek fark indeksleme ve işaretleme stratejisi.
Küçük optimizasyonlarla büyük aralıklarda bile performans artışı sağlar.

Zaman Karmaşıklığı: O(n log log n) - klasik kalburla aynı, ancak yalnızca tek sayılar işlendiği için sabit faktör daha küçük.
Bellek Karmaşıklığı: O(n/2) ≈ O(n) - çift sayılar tutulmadığı için yaklaşık yarı bellek tasarrufu sağlanıyor.

💻 Çalıştıralım

  
[fr0stb1rd@archlinux demo]$ nano sieve_odd.cpp
[fr0stb1rd@archlinux demo]$ g++ sieve_odd.cpp -o sieve_odd -O2
[fr0stb1rd@archlinux demo]$ ./sieve_odd 
2 3 5 7 11 13 17 19 23 29 
[fr0stb1rd@archlinux demo]$ 

🛞 Çark (Wheel) Sieve - 6k ± 1 Optimizasyonu

  
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> sieve_wheel(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 4; i <= n; i += 2) is_prime[i] = false;
    for (int i = 9; i <= n; i += 6) is_prime[i] = false;
    int limit = sqrt(n);
    for (int i = 5, step = 2; i <= limit; i += step, step = 6 - step) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i * 2)
                is_prime[j] = false;
        }
    }
    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) primes.push_back(i);
    return primes;
}

int main() {
    int n = 30;
    auto primes = sieve_wheel(n);
    for (int p : primes) cout << p << " ";
    cout << "\n";
}

💡 Wheel (çark) fikri

Burada amaç: bazı sayı kümelerini (çiftler, 3’ün katları) en baştan elemek, böylece dış döngüde daha az iş yapmak.
Kullanılan en küçük çark: 2 ve 3 tabanlı wheel (6’lık çark).
- Yani asal olabilecek adaylar yalnızca 6k ± 1 şeklinde.

🚦 Başlangıç eleme adımları

  
for (int i = 4; i <= n; i += 2) is_prime[i] = false;  // çiftler çıkar
for (int i = 9; i <= n; i += 6) is_prime[i] = false;  // 3’ün bazı katları çıkar

Önce tüm çift sayılar elendi.
Sonra 9, 15, 21, … gibi 3’ün katları da elendi (özellikle 6k+3 olanlar).

🔂 Döngüde 6 adımlı ilerleme

  
for (int i = 5, step = 2; i <= limit; i += step, step = 6 - step)

Bu yazım hilesi sayesinde i sırasıyla: 5, 7, 11, 13, 17, 19, … şeklinde yalnızca 6k ± 1 sayılarında dolaşır.
Böylece zaten asal olamayacak sayıların üzerinden hiç geçilmez.

✖️ Katları işaretleme

  
for (int j = i * i; j <= n; j += i * 2)
    is_prime[j] = false;

Burada j += i*2 olmasının sebebi, Zaten çift sayılar en başta çıkarıldığı için, her adımda tek katlara bakıyoruz. Bu da iş yükünü yarı yarıya azaltıyor.

📋 Asalları toplama

  
for (int i = 2; i <= n; i++)
    if (is_prime[i]) primes.push_back(i);

Eleme bittikten sonra geriye kalan tüm true değerli indeksler asal olarak vektöre ekleniyor.

🧩 Algoritma

Basit sieve -> tüm sayıları kontrol eder.
Odd sieve -> yalnızca tek sayıları kontrol eder.
Wheel sieve (mod 6) -> yalnızca 6k ± 1 sayılarıyla ilgilenir.
Bu yöntemle:
- Çalışma süresi azalır.
- Eleme daha düzenli olur.
- Özellikle büyük n değerlerinde performans kazancı sağlar.

Zaman Karmaşıklığı: O(n log log n) - klasik kalburla aynı ama sabit faktör daha küçük, çünkü sadece 6k ± 1 adayları deneniyor.
Bellek Karmaşıklığı: O(n) - tüm 0..n aralığı için is_prime tutuluyor.

💻 Çalıştıralım

  
[fr0stb1rd@archlinux demo]$ nano sieve_wheel.cpp
[fr0stb1rd@archlinux demo]$ g++ sieve_wheel.cpp -o sieve_wheel -O2
[fr0stb1rd@archlinux demo]$ ./sieve_wheel 
2 3 5 7 11 13 17 19 23 29 
[fr0stb1rd@archlinux demo]$ 

🧩 Segmentli Sieve - Büyük Aralıklar İçin

  
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> simple_primes(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (is_prime[p]) {
            for (int i = p * p; i <= n; i += p)
                is_prime[i] = false;
        }
    }
    vector<int> primes;
    for (int i = 2; i <= n; i++)
        if (is_prime[i]) primes.push_back(i);
    return primes;
}

vector<int> sieve_segment(long long L, long long R) {
    long long limit = sqrt(R);
    auto primes = simple_primes(limit);
    vector<bool> is_prime(R - L + 1, true);
    for (long long p : primes) {
        long long start = max(p * p, ((L + p - 1) / p) * p);
        for (long long j = start; j <= R; j += p)
            is_prime[j - L] = false;
    }
    vector<int> result;
    for (long long i = L; i <= R; i++) {
        if (i > 1 && is_prime[i - L]) result.push_back((int)i);
    }
    return result;
}

int main() {
    long long L = 1, R = 30;
    auto primes = sieve_segment(L, R);
    for (int p : primes) cout << p << " ";
    cout << "\n";
}

📑 Küçük asal listesi

  
long long limit = sqrt(R);
auto primes = simple_primes(limit);

Aralık [L, R] için asal bulmak istiyoruz.
Bunun için sadece sqrt(R)’e kadar olan küçük asal sayılar yeterli.
O küçük asallar simple_primes fonksiyonuyla bulunuyor.

🗂️ Aralık için ayrı asal tablosu

  
vector<bool> is_prime(R - L + 1, true);

Bu dizi yalnızca [L, R] aralığını temsil ediyor.
Mesela L=10, R=20 ise, dizi boyutu 11 olur ve indeks i-L mantığıyla gerçek sayılara karşılık gelir.

✖️ Küçük asallarla çarpanları işaretleme

  
long long start = max(p * p, ((L + p - 1) / p) * p);
for (long long j = start; j <= R; j += p)
    is_prime[j - L] = false;

Burada kritik kısım hangi noktadan işaretlemeye başlanacağı.
p*p -> her asalın kendi karesinden önceki katlarını işaretlemeye gerek yok (çünkü daha küçük asal çarpanlarla zaten elenmiş olurlar).
((L + p - 1) / p) * p -> [L, R] aralığındaki ilk p katı bulunuyor.
İkisi arasında büyük olan seçiliyor (max) -> doğru başlangıç noktası garanti ediliyor.
Sonra j += p ile ilerleyip çarpanlar eleniyor.

📋 Asalları toplama

  
for (long long i = L; i <= R; i++) {
    if (i > 1 && is_prime[i - L]) result.push_back((int)i);
}

[L, R] aralığındaki asal sayılar result vektörüne ekleniyor.
i > 1 kontrolü -> çünkü 1 asal değil.

🧩 Algoritma

Segmentli sieve, çok büyük sayılarla çalışmak için uygundur.
Avantajı:
- is_prime dizisi yalnızca [L, R] aralığını tutar -> bellek tasarrufu.
- Çok büyük R değerlerinde, tüm 0..R dizisini saklamak zorunda kalmayız.
Küçük asallar bir kez bulunur -> sonra yalnızca aralıkta kullanılır.

Zaman Karmaşıklığı: O((R − L + 1) log log R)
Bellek Karmaşıklığı: O(R − L + 1)

💻 Çalıştıralım

  
[fr0stb1rd@archlinux demo]$ nano sieve_segment.cpp
[fr0stb1rd@archlinux demo]$ g++ sieve_segment.cpp -o sieve_segment -O2
[fr0stb1rd@archlinux demo]$ ./sieve_segment 
2 3 5 7 11 13 17 19 23 29 
[fr0stb1rd@archlinux demo]$ 

⏱️ Ölçümler

  
[fr0stb1rd@archlinux demo]$ hyperfine \
  --shell=none \
  --warmup 5 \
  -r 5000 \
  './sieve_simple > /dev/null' \
  './sieve_odd > /dev/null' \
  './sieve_wheel > /dev/null' \
  './sieve_segment > /dev/null' 

Benchmark 1: ./sieve_simple > /dev/null
  Time (mean ± σ):       1.6 ms ±   0.3 ms    [User: 0.9 ms, System: 0.6 ms]
  Range (min … max):     0.7 ms …   2.7 ms    5000 runs
 
Benchmark 2: ./sieve_odd > /dev/null
  Time (mean ± σ):       1.6 ms ±   0.3 ms    [User: 0.9 ms, System: 0.6 ms]
  Range (min … max):     0.6 ms …   2.9 ms    5000 runs
 
Benchmark 3: ./sieve_wheel > /dev/null
  Time (mean ± σ):       1.3 ms ±   0.5 ms    [User: 0.7 ms, System: 0.5 ms]
  Range (min … max):     0.7 ms …   2.5 ms    5000 runs
 
Benchmark 4: ./sieve_segment > /dev/null
  Time (mean ± σ):     924.1 µs ± 264.0 µs    [User: 512.2 µs, System: 346.1 µs]
  Range (min … max):   681.6 µs … 3699.5 µs    5000 runs
 
Summary
  ./sieve_segment > /dev/null ran
    1.36 ± 0.63 times faster than ./sieve_wheel > /dev/null
    1.71 ± 0.61 times faster than ./sieve_odd > /dev/null
    1.74 ± 0.60 times faster than ./sieve_simple > /dev/null
[fr0stb1rd@archlinux demo]$ 

⚡ Performans Karşılaştırması

Dört farklı Eratosthenes kalburu uygulamasını aynı sayı aralığında test ettik ve çalışma sürelerini Hyperfine ile ölçtük. Ölçümlerde çıktı ekrana yazdırılmadı (> /dev/null) ve her yöntem 5000 kez çalıştırıldı.

Yöntem	Ortalama Süre	Min - Max
Simple Sieve	1.6 ms	0.7 - 2.7 ms
Odd Sieve	1.6 ms	0.6 - 2.9 ms
Wheel Sieve	1.3 ms	0.7 - 2.5 ms
Segmented Sieve	924 µs	682 - 3700 µs

🔍 Analiz

sieve_simple ve sieve_odd çok benzer hızda çalışıyor; küçük optimizasyonlar (tek sayılar üzerinden eleme) büyük fark yaratmamış.
sieve_wheel ile bazı sayıların baştan elenmesi, çalışma süresini yaklaşık %20 hız kazancı ile düşürmüş.
Segmented Sieve, aralık bazlı çalışması sayesinde en hızlı yöntem olmuş; diğerlerine göre yaklaşık 1.7 kat daha hızlı.

💡 Not: Ölçümlerde küçük sapmalar (σ) ve min/max değerler gözlemlenebilir, çünkü CPU zamanlaması ve sistem yükü küçük etkiler yaratabiliyor. Büyük sayı aralıklarında farklar çok daha belirgin hale gelir.

📊 Grafik

🚀 Diğer Yöntemler ve İleri Optimizasyonlar

Özellikle büyük sayı aralıkları veya yüksek performans gereken durumlarda kullanılan birkaç yöntem daha vardır.

1️⃣ Bitset Tabanlı Sieve

vector<bool> yerine std::bitset veya manuel bit dizileri kullanılır.
Bellek kullanımı ciddi şekilde azalır, çünkü her sayı için yalnızca 1 bit gerekir.
Büyük n değerlerinde CPU cache avantajı sağlar ve hız kazandırır.

2️⃣ Atkin Sieve (Sieve of Atkin)

Modern bir asal sayılar süzgeci.
Belirli modüler denklemlerle asal adaylarını hızlıca belirler.
Çok büyük sayılar için klasik Eratosthenes Sieve’den daha hızlı olabilir.
Dezavantaj: Algoritması daha karmaşık ve implementasyonu zor.

3️⃣ Paralel / GPU Destekli Sieve

Çok çekirdekli CPU veya GPU üzerinde eş zamanlı olarak kalbur uygulanır.
Segmentli veya wheel sürümleri ile birleştiğinde devasa aralıklar için hız kazancı sağlar.
Örnek: CUDA veya OpenCL ile GPU hızlandırmalı implementasyonlar.

4️⃣ Cache-Optimized Sieve

Bellek erişimlerini CPU cache’e uygun şekilde düzenler.
Büyük n değerlerinde klasik sieve’in bellek erişim gecikmesini azaltır.
Teknik olarak segmentli sieve ile yakın ilişkilidir, ancak daha ince cache segmentasyonu yapar.

5️⃣ Gelişmiş Wheel Sieve

6k ± 1 kuralının ötesine geçilerek daha büyük çarklar kullanılabilir.
Örnekler:
- 30 tabanlı wheel → 2, 3, 5 asal sayılarını dışarıda bırakır.
- 210 tabanlı wheel → 2, 3, 5, 7 asal sayılarını dışarıda bırakır.
Amaç: Daha az sayı üzerinden eleme yaparak büyük aralıklar için sabit faktörü düşürmek.

6️⃣ Önceden Hesaplanmış Asallar (Memoization)

Sık kullanılan aralıklar veya uygulamalarda, küçük asal sayılar önceden hesaplanıp saklanır.
Örnek: [2, 10^6] aralığı bir kere hesaplanır ve sonraki işlemlerde yeniden kullanılır.
Böylece aynı aralıkta tekrar hesaplama yapılmasına gerek kalmaz.

7️⃣ Analitik / Test Tabanlı Yöntemler

Sieve olmamakla birlikte, Miller-Rabin veya AKS primality testleri ile büyük tek sayılar üzerinde asal kontrolü yapılabilir.
Özellikle tek tek asal kontrolü gereken durumlarda kullanılır.

📋 Karşılaştırma Tablosu

Yöntem	Bellek Kullanımı	Zaman Karmaşıklığı	Özellik / Avantaj
Simple Sieve	O(n)	O(n log log n)	Basit ve anlaşılır
Odd Sieve	≈ O(n/2)	O(n log log n)	Tek sayılar üzerinden bellek tasarrufu
Wheel Sieve (6k ± 1)	O(n)	O(n log log n)	Sabit faktör daha küçük, daha hızlı
Gelişmiş Wheel Sieve	O(n)	O(n log log n)	Daha büyük çarklar (30, 210 tabanlı) ile daha az eleme
Segmentli Sieve	O(R-L+1)	O((R-L+1) log log R)	Büyük aralıklar için bellek tasarrufu
Bitset Sieve	O(n/8)	O(n log log n)	Bellek kullanımını ciddi azaltır
Atkin Sieve	O(n)	O(n) teorik / pratikte hızlı	Çok büyük sayılarda klasik Sieve’den hızlı
Paralel / GPU Sieve	O(R-L+1)	Donanıma ve segment boyutuna bağlı	Büyük aralıkları eş zamanlı hızlı işler
Cache-Optimized Sieve	O(R-L+1)	Donanıma ve segment boyutuna bağlı	CPU cache’e uygun, büyük `n` için optimize
Önceden Hesaplanmış (Memo)	Uygulamaya bağlı	Tekrar kullanım hızlı	Sık aralıklar için zaman kazancı
Analitik / Test Tabanlı	O(1)	O(k) veya O(log n)	Miller-Rabin, AKS gibi primality testleri, tek tek kontrol

📚 Sözlük

🟢 Asal Sayı

Kendisi ve 1 dışında böleni olmayan 1’den büyük doğal sayılar.
Örnek: 2, 3, 5, 7, 11, 13 …

🔴 Bileşik Sayı

1’den büyük olup asal olmayan sayı.
Yani en az iki farklı böleni var.
Örnek: 4 (2×2), 6 (2×3), 9 (3×3).

🧺 Kalbur (Sieve)

Asal olmayanları sistematik biçimde elemeye yarayan algoritma yaklaşımı.
Adını, elenen sayıların “elekten geçmesi” fikrinden alır.