Asal Sayı Bulma Algoritması (Eratosthenes Kalburu) C Kodu
Eratosthenes Kalburu yada bizdeki adıyla Eratosten Kalburu (Sieve of Eratosthenes) bir n sayısına kadar olan asal sayıları bulmamıza olanak sağlayan bir algoritmadır. Eski Yunanlılar döneminde Eratosthenes tarafından geliştirilen algoritma bugünde asal sayı bulma algoritmaları arasında yerini korumaktadır. Bu yazımızda kısaca Eratosten Kalburu, 2'den belli bir sayıya kadar olan asal sayıları bulma algoritmasını inceleyeceğiz ve C programlama dilinde kodunu paylaşacağız.
Asal Sayı Bulma Algoritması (Eratosthenes Kalburu)
Eratosten Kalburunun çalışma mantığı şu şekildedir:
-- 0'dan N sayısına kadar olan asal sayıları bulmak istediğimizi varsayalım.
-- Algoritmamıza 2 sayısından başlıyoruz. 2' den N' e kadar olan 2' nin bütün katlarını işaretleyin. Bu sayılar asal değildir.
-- Aynı işlemi 3 sayısının katları için uygulayın.
-- Buradan sonra 2 ve 3 ten sonra gelen ve işaretli olmayan sayılar için uyguluyoruz.
-- Durma noktamız ise N sayısını kareköküdür.
-- Durduktan sonra elimizde kalan işaretsiz sayılar 0'dan N' e kadar olan asal sayıları verecektir.
Gördüğümüz gibi mantığını kavraması son derece basit olan Eratosten Kalburu algoritmasının şimdi de C programlama dilinde nasıl yazabiliriz ona bakalım.
[B][B]Asal Sayı Bulma Algoritması (Eratosthenes Kalburu) C Kodu[/B][/B]
#include
#include
int main(){
int i,j,x;
int *asalSayilar;
printf("Sayi: "); scanf("%d",&x); // X sayısına kadar olan asal sayıları bulacağız.
asalSayilar=(int *)malloc(x*sizeof(int)); // X boyutunda bir dizi oluşturduk.
for (i=2;i<(x);i++){ // Dizinin elemanlarını 1'e eşitledik.
asalSayilar=1;
}
// 2'den X'in kareköküne kadar olan ve daha önce işaretlemediğimiz sayıların katlarını 0'a eşitleyerek işaretliyoruz.
for (i=2;i
for (j=i;i*j
}
}
}
j=0;
// İşaretlenmemiş sayıları ekrana yazdıralım.
for (i=2;i
printf("%d. Asal Sayi = %d\n",j++,i);
return 0;
}
[I]Kod Analiz:
-- İlk olarak kullanıcıdan kendisine kadar olan asal sayıları bulacağımız X sayısını aldık.
-- Daha sonra X boyutunda bir dizi oluşturduk ve elemanlarını 1'e eşitledik.
-- Asıl Eratosten algoritmasının işlendiği kısımda ise bir for döngüsü ile 2'den X sayısının kareköküne kadar olan sayılar için daha önce işaretlenmemiş olanların X sayısına kadar olan katlarını 0'a eşitledik. Böylece onları işaretlemiş olduk.
-- Son kısımda ise işaretlenmemiş yani 0'a eşitlemediğimiz kısımları ekrana bastırdık. Bu kısımlar X'e kadar olan asal sayılara eşittir.
Şimdi de yukarıdaki kod için elde ettiğimiz ekran görüntülerine bir göz atalım.
Ekran Görüntüleri:
Yazdığımız kodu 30 ve 100 sayıları için çalıştırdık ve doğru sonucu elde ettik. Kısaca Erastoten Kalburu algoritmasını özetleyelim. Erastoten Kalburu 0'dan bir N sayısına kadar olan sayılar içerisindeki asal sayıları 2'den başlayarak daha önce işaretlenmemiş olan sayıların katlarını N sayısını geçmeyecek şekilde ve N sayısının kareköküne kadar işaretler. Kalan sayılar ise bulmak istediğimiz asal sayılar olur.
"Asal Sayı Bulma Algoritması (Eratosthenes Kalburu) C Kodu" adlı bu makale işinize yaradıysa yorum yapmayı ve paylaşmayı unutmayın.
Kaynak: Pubtekno
