Asal Sayı Bulma Algoritması (Eratosthenes Kalburu)

Merhaba arkadaşlar,
Mobilhanem.com üzerinden anlattığımız/yayınladığımız Algoritma Eğitimleri serimize devam ediyoruz. Bu dersimizde ise Eratosthenes Kalburu algoritmasını anlatmaya çalışacağız.

Problem Nedir?

Size bir n sayısı veriliyor. Sizden 1’den n’e kadar olan asal sayıları bulmanız isteniyor.

Bir sayının asal olup olmadığını anlamak için akla gelen ilk yöntem şöyledir: 2’den kontrol edeceğimiz sayıya kadar döngü açılıp tek tek bölünüyor mu diye kontrol etmemiz gerekir. Bize verilen problemde tek bir sayının değil de n’e kadar bütün sayıları asal mı değil mi diye kontrol etmemiz gerektiği için bu yöntemin maliyeti O(N^2) olacaktır.

Biz şimdi Eratosthenes Kalburunun kullanarak bu maliyeti O(N)‘e indireceğiz.

Eratosthenes Kalburu Nedir?

1’den 10^7’ye kadar olan asal sayıların tümünü bulmamızı sağlayan Eratosthenes Kalburun kodunu vererek anlatmaya başlayalım.

    bool prime[n+1];
    memset(prime, true, sizeof(prime));
 
    for (int p=2; p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*2; i<=n; i += p)
                prime[i] = false;
        }
    }
 
    for (int p=2; p<=n; p++)
       if (prime[p])
          cout << p << " ";

Öncelikle prime diye bir bool veri tipinde dizi tanımlıyoruz. Başlangıçta bu dizinin bütün elemanlarını true yapıyoruz. Algoritmanın sonunda yalnızca asal olan sayıların true olmasını istiyoruz ve asal olmayanlara false değerini atamaya çalışıyoruz.

Algoritmanın temel mantığını anlatmak gerekirse bir asal sayı alıyoruz ve biz biliyoruz ki bu asal sayının hiçbir tam katı asal değildir. Örnek vermek gerekirse 5 bir asal sayıdır ancak 5 in tam katları olan 10,15,20,25… şeklinde giden sayıların hiçbiri asal değildir. Çünkü en azından 5’e bölüneceği garantidir.

Kod Açıklaması

İlk döngü 1’den başlayarak n’e kadar sayıları geziyor. İçerdeki if kontrolü sayının asal olup olmadığını kontrol ediyor eğer sayı asal ise bütün tam katlarını gezerek asal olmadığından emin olduğumuz için false değerini atıyor.

En sonunda ise değeri hala true olarak kalan sayıları ekrana yazdırarak 1’den n’e kadar olan bütün asalları bulmamızı sağlıyor.

Maliyet Hesaplaması

Üstteki for döngüsünden N maliyet geliyor alttaki döngünün yaptığı işlemler git gide azalıyor.
p=2 için n/2
p=3 için n/3
p=4 için n/4
.
.
.
p=n için n/n=1 işlem yapılır.
Yani alttaki for toplamda N işlem yaptığı için Algoritmanın maliyeti O(N) olmaktadır.

Diğer Popüler Dillerdeki Kodlaması:

Java

void sieveOfEratosthenes(int n)
    {
        
        boolean prime[] = new boolean[n+1];
        for(int i=0;i<n;i++)
            prime[i] = true;
         
        for(int p = 2; p*p <=n; p++)
        {
            
            if(prime[p] == true)
            {
                
                for(int i = p*2; i <= n; i += p)
                    prime[i] = false;
            }
        }
         
     
        for(int i = 2; i <= n; i++)
        {
            if(prime[i] == true)
                System.out.print(i + " ");
        }
    }

Python

def SieveOfEratosthenes(n):
         prime = [True for i in range(n+1)]
    p = 2
    while (p * p <= n):
         
       
        if (prime[p] == True):
             
            
            for i in range(p * 2, n+1, p):
                prime[i] = False
        p += 1
     
  
    for p in range(2, n):
        if prime[p]:
            print p,

Okuduğunuz için teşekkür ederim umarım faydalı olmuşumdur. Takıldığınız noktaları ve her türlü sorularınızı aşağıdan veya Soru Cevap kısmından sormayı lütfen eksik etmeyin. Bir sonraki Algoritma Eğitiminde görüşmek üzere. Sağlıcakla kalın.

Tüm Algoritma Derslerimiz İçin tıklayınız.