Matematikte, Eratosthenes(Eratosten) Eleği belirli bir tamsayıya kadar yer alan asal sayıların bulunması için kullanılan bir yöntemdir. Daha hızlı ve karmaşık olan Atkin kalburunun atası sayılır. Eski Yunan'da Eratosten tarafından geliştirilmiştir.
Eratosthenes Alexandria da ve bir müddet Atina da öğrenim görmüştür. İ.Ö.236 da Ptolemy III Euergetes I tarafından Alexandria Kütüphanesine, o koltuktaki ilk kütüphaneci Zenodotos'un ardından, kütüphaneci olarak atanmıştır. Matematik ve doğal bilimlere katkılarda bulunmuştur. İ.Ö.195 de kör olmuştur ve bir yıl sonra kasıtlı olarak kendini aç bırakarak ölmüştür.
Elegin işleyişi :
1. Önce bir dizelgeye 2'den başlayarak, istediğiniz en büyük tam sayıya kadar olan tüm tamsayıları yazın. Bu dizelgenin adı A olsun.
2. Bir diğer dizelgeye A'daki ilk asal sayı olan 2'den başlayarak bulduğunuz asal sayıları yazın. Bu dizelgenin adı B olsun.
3. A'dan 2'yi ve 2'nin tüm katlarını silin.
4. A'da kalan ilk tek sayı asaldır. Bu sayıyı B'ye ekleyin
5. Bu sayıyı ve tüm katlarını A'dan silin. Daha küçük katları zaten silindiğinden, silme safhası bu sayının karesinden başlayabilir.
6. A dizelgesinde herhangi bir sayı kalmayıncaya kadar 4. ve 5. adımları tekrarlayın
Merhaba,
Bu makalemizde C dilinde Eratosten eleğini kodlayarak iki tamsayı arasında bulunan asal sayıları bulacağız. İnternette araştırırsanız farklı kodlanmış elek kodlarına rastlayabilirsiniz. Yukarıdaki örnek animasyonda eleğin nasıl çalıştığı görülmekte.
Eratosten eleğini kaynak kodlarını aşağıda görebilirsiniz veya CodeBlock proje dosyasını bilgisayarınıza indirip inceleyebilirsiniz. Sorularınız için bana yazabilirsiniz. Bir başka makalede buluşmak dilegiyle.
CodeBlocks Proje Dosyası : Eratosten_elek_project.rar (10,61 kb)
/*============================================================*/
/* Program : Eratosten Elegi */
/* Yazan : Zafer ÇELENK */
/* Tarih : 19.01.2009 */
/* E-Posta : zafercelenk@gmail.com */
/* */
/* Aciklama : Asal sayıları bulmak için kullanılan Eratosten eleginin C dilinde kodlanması */
/* */
/*============================================================*/
#include <stdio.h>
#include <stdlib.h>
#define SIZE 120
void InitializeSieve(int aSieve[], int aSize);
void RunSieve(int aSieve[]);
void PrintSieve(int aSieve[]);
int main()
{
int sieve[SIZE]; /* Tüm sayıları tutan dizimiz */
InitializeSieve(sieve, SIZE);
RunSieve(sieve);
PrintSieve(sieve);
return 0;
}
void RunSieve(int aSieve[])
{
int multiple = 0; /* ilgilendigiimiz sayıların katlarını belitren degikenimiz */
int result = 0; /* sayı * kat sonucunda elde edecegimiz sonuc, yani elekten elenecek sayı */
int i;
for (i=2; i<=SIZE; i++)
{
multiple = i; /* Carpanını ilgilendigimiz sayının katlarını verecek sekilde ayarlıyoruz */
while (result < SIZE)
{
result = multiple * i;
/* printf("i: %d, mutiple: %d, result: %d\n", i, multiple, result); */
if (result <= SIZE) /* Eger sayının katı ilgilendigimiz aralıktaysa islem yapıyoruz */
aSieve[result] = 0;
multiple++;
}
result = 0;
}
}
void PrintSieve(int aSieve[])
{
int i;
printf("\n\nElek dizimiz (1-%d) :\n\n", SIZE);
for (i=1; i<=SIZE; i++)
printf("%3d%c", aSieve[i], (i % 10 == 0) ? '\n' : ' ');
printf("\n\nBelirtilen (1-%d) sayi araligindaki asal sayilar:\n\n", SIZE);
for (i=2; i<=SIZE; i++)
{
if (aSieve[i] > 0)
printf("%d, ", aSieve[i]);
}
printf("\n\n");
}
void InitializeSieve(int aSieve[], int aSize)
{
int i;
for (i=1; i<=aSize; i++)
aSieve[i] = i;
}
Etiketler: eratosten, elek