Eratosthenes Kalburu'nda Python & C++
Sarah Chen
โก Akฤฑllฤฑ รzet
Eratosthenes Kalburu, bileลik sayฤฑlarฤฑ filtreleyen klasik bir asal sayฤฑ algoritmasฤฑdฤฑr; her asal sayฤฑnฤฑn katlarฤฑnฤฑ yinelemeli olarak iลaretleyerek, yalnฤฑzca seรงilen bir รผst sฤฑnฤฑr iรงindeki asal sayฤฑlarฤฑ hฤฑzlฤฑ arama iรงin bฤฑrakฤฑr.
Eratosthenes Kalburu Nedir?
Eratosthenes Kalburu, en basit asal sayฤฑ kalburudur. Belirli bir sฤฑnฤฑr iรงindeki tรผm asal sayฤฑlarฤฑ bulmak iรงin kullanฤฑlan bir asal sayฤฑ algoritmasฤฑdฤฑr. Eratosthenes Kalburu, Atkin Kalburu ve Sundaram Kalburu dahil olmak รผzere รงeลitli asal sayฤฑ kalburlarฤฑ mevcuttur.
Kelime "elek"Elek" terimi, maddeleri filtreleyen bir aleti ifade eder. Aynฤฑ mantฤฑkla, elek algoritmasฤฑ da bu doฤrultudadฤฑr. Python ve diฤer diller, tamsayฤฑlar listesinden asal sayฤฑlarฤฑ ayฤฑklamak iรงin kullanฤฑlan bir yรถntemi ifade eder.
Bu algoritma, yinelemeli bir yaklaลฤฑm kullanarak asal sayฤฑlarฤฑ filtreler. Filtreleme iลlemi en kรผรงรผk asal sayฤฑdan baลlar. Asal sayฤฑ, 1'den bรผyรผk ve yalnฤฑzca iki bรถleni olan doฤal sayฤฑdฤฑr; bu bรถlenler 1 ve sayฤฑnฤฑn kendisidir. Numbers Asal olmayan sayฤฑlara bileลik sayฤฑlar denir.
Eratosthenes eleฤi neden kullanฤฑlฤฑr?
Eratosthenes Kalburu yรถnteminde, รถnce kรผรงรผk bir asal sayฤฑ seรงilir ve bu sayฤฑnฤฑn tรผm katlarฤฑ elenir. Bu iลlem, verilen bir aralฤฑkta dรถngรผ halinde รงalฤฑลarak, her aday รผzerinde deneme bรถlmesi yapmadan n'ye kadar olan tรผm asal sayฤฑlarฤฑ verimli bir ลekilde รผretir.
Bu yรถntem, asal sayฤฑlarฤฑ tek tek kontrol etmekten daha hฤฑzlฤฑ bir eleme yรถntemi sunar. Sayฤฑ teorisi, kriptografi, karma fonksiyonlar ve birรงok asal sayฤฑnฤฑn hฤฑzlฤฑ bir ลekilde รผretilmesi gereken rekabetรงi programlama gibi alanlarda yaygฤฑn olarak kullanฤฑlฤฑr.
รrneฤin:
2 ile 10 arasฤฑndaki sayฤฑ aralฤฑฤฤฑnฤฑ ele alalฤฑm.
Eratosthenes Kalburu uygulandฤฑktan sonra, 2, 3, 5, 7 asal sayฤฑlarฤฑnฤฑn listesi elde edilecektir.
Eratosthenes'in Algoritma Eleฤi
ฤฐลte Eratosthenes Eleฤinin algoritmasฤฑ:
) 1 Adฤฑm Verilen n aralฤฑฤฤฑndan baลlayarak 2'den itibaren sayฤฑlarฤฑn bir listesini oluลturun. En kรผรงรผk ve ilk asal sayฤฑ olduฤu iรงin 2 ile baลlฤฑyoruz.
) 2 Adฤฑm Listedeki en kรผรงรผk sayฤฑyฤฑ, x'i (baลlangฤฑรงta x 2'ye eลittir), seรงin, listeyi tarayฤฑn ve seรงilen sayฤฑnฤฑn tรผm katlarฤฑnฤฑ iลaretleyerek karลฤฑlฤฑk gelen bileลik sayฤฑlarฤฑ filtreleyin.
) 3 Adฤฑm Daha sonra listedeki bir sonraki asal sayฤฑyฤฑ veya iลaretlenmemiล en kรผรงรผk sayฤฑyฤฑ seรงin ve 2. adฤฑmฤฑ tekrarlayฤฑn.
) 4 Adฤฑm x deฤeri n'nin karekรถkรผnden kรผรงรผk veya ona eลit olana kadar รถnceki adฤฑmฤฑ tekrarlayฤฑn (x<=
).
Not: Matematiksel mantฤฑk oldukรงa basittir. n sayฤฑ aralฤฑฤฤฑ ลu ลekilde รงarpanlarฤฑna ayrฤฑlabilir:
n = a * b
Yine n = *
= (faktรถr daha kรผรงรผk ) * (faktรถr ลundan bรผyรผk: )
Yani en az bir tanesi asal faktรถrler veya her ikisi de <= olmalฤฑdฤฑr Bu nedenle, yukarฤฑya doฤru ilerlemek yeterli olacak.
) 5 Adฤฑm Bu dรถrt adฤฑmdan sonra, iลaretlenmemiล kalan sayฤฑlar, verilen n aralฤฑฤฤฑndaki tรผm asal sayฤฑlar olacaktฤฑr.
Uygulamalฤฑ รrnek
รrnek:
Bir รถrnek รผzerinden nasฤฑl iลlediฤine bakalฤฑm.
Bu รถrnekte, 2'den 25'e kadar olan asal sayฤฑlarฤฑn listesini bulacaฤฤฑz. Yani, n = 25.
) 1 Adฤฑm ฤฐlk adฤฑmda, n = 25 seรงtiฤimiz iรงin 2'den 25'e kadar olan sayฤฑlarฤฑn bir listesini alacaฤฤฑz.
) 2 Adฤฑm Ardฤฑndan listedeki en kรผรงรผk sayฤฑyฤฑ, x'i seรงiyoruz. Baลlangฤฑรงta x = 2 รงรผnkรผ en kรผรงรผk asal sayฤฑdฤฑr. Daha sonra listeyi dolaลฤฑp 2'nin katlarฤฑnฤฑ iลaretliyoruz.
Verilen n deฤeri iรงin 2'nin katlarฤฑ ลunlardฤฑr: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.
Not: Mavi renk seรงilen sayฤฑyฤฑ, pembe renk ise elenen katlarฤฑ gรถsterir.
) 3 Adฤฑm Daha sonra bir sonraki en kรผรงรผk iลaretsiz sayฤฑ olan 3'รผ seรงiyoruz ve 3'รผn katlarฤฑnฤฑ iลaretleyerek son adฤฑmฤฑ tekrarlฤฑyoruz.
) 4 Adฤฑm x = olana kadar 3. adฤฑmฤฑ aynฤฑ ลekilde tekrarlฤฑyoruz. 
veya 5.
) 5 Adฤฑm ฤฐลaretlenmemiล kalan sayฤฑlar ise 2 ile 25 arasฤฑndaki asal sayฤฑlardฤฑr.
yalancฤฑCode
Aลaฤฤฑdaki sรถzde kod, Eratosthenes Kalburu'nun temel yapฤฑsฤฑnฤฑ, gerรงek koda รงevirmeden รถnce gรถstermektedir.
Begin
Declare a boolean array of size n and initialize it to true
For all numbers i : from 2 to sqrt(n)
IF bool value of i is true THEN
i is prime
For all multiples of i (i<n)
mark multiples of i as composite
Print all unmarked numbers
End
Eratostenes Eleฤi C/C++ Code รrnek E-posta
Aลaฤฤฑda eksiksiz bir liste bulunmaktadฤฑr. C++ Seรงilen bir รผst sฤฑnฤฑra kadar olan tรผm asal sayฤฑlarฤฑ yazdฤฑran Eratosthenes Kalburu'nun uygulanmasฤฑ.
#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
// Create and initialize a boolean array
bool primeNumber[n + 1];
memset(primeNumber, true, sizeof(primeNumber));
for (int j = 2; j * j <= n; j++) {
if (primeNumber[j] == true) {
// Update all multiples of i as false
for (int k = j * j; k <= n; k += j)
primeNumber[k] = false;
}
}
for (int i = 2; i <= n; i++)
if (primeNumber[i])
cout << i << " ";
}
int main()
{
int n = 25;
Sieve_Of_Eratosthenes(n);
return 0;
}
รฤฑktฤฑ:
2 3 5 7 11 13 17 19 23
Eratosthenes Elekleri Python Program รrneฤi
Aลaฤฤฑdaki Python Program, aynฤฑ algoritmayฤฑ bir boolean listesi ve bir while dรถngรผsรผ kullanarak uygular.
def SieveOfEratosthenes(n): # Create a boolean array primeNumber = [True for i in range(n+2)] i = 2 while (i * i <= n): if (primeNumber[i] == True): # Update all multiples of i as false for j in range(i * i, n+1, i): primeNumber[j] = False i += 1 for i in range(2, n): if primeNumber[i]: print(i) n = 25 SieveOfEratosthenes(n)
รฤฑktฤฑ:
2 3 5 7 11 13 17 19 23
Parรงalฤฑ Elek
Eratosthenes Kalburu'nun tรผm sayฤฑ aralฤฑฤฤฑ boyunca bir dรถngรผ รงalฤฑลtฤฑrdฤฑฤฤฑnฤฑ gรถrdรผk. Bu nedenle, sayฤฑlarฤฑ depolamak iรงin O(n) bellek alanฤฑna ihtiyaรง duyar. รok bรผyรผk bir aralฤฑkta asal sayฤฑlarฤฑ bulmaya รงalฤฑลtฤฑฤฤฑmฤฑzda durum karmaลฤฑklaลฤฑr, รงรผnkรผ daha bรผyรผk bir n iรงin bu kadar bรผyรผk bir bellek bloฤu ayฤฑrmak mรผmkรผn deฤildir.
Algoritma bazฤฑ yeni รถzellikler eklenerek optimize edilebilir. Fikir, sayฤฑ aralฤฑฤฤฑnฤฑ daha kรผรงรผk parรงalara bรถlmek ve bu parรงalardaki asal sayฤฑlarฤฑ tek tek hesaplamaktฤฑr. Bu, alan karmaลฤฑklฤฑฤฤฑnฤฑ azaltmanฤฑn etkili bir yoludur. Bu yรถnteme bir bรถlรผmlรผ elek.
Optimizasyon aลaฤฤฑdaki ลekilde saฤlanabilir:
- 2'den XNUMX'ye kadar asal sayฤฑlarฤฑ bulmak iรงin basit bir elek kullanฤฑn
ve bunlarฤฑ bir dizide saklayฤฑn. - [0โฆn-1] aralฤฑฤฤฑnฤฑ en fazla birden fazla boyut segmentine bรถlรผn .
- Her bir segment iรงin, segmenti yineleyin ve 1. adฤฑmda bulunan asal sayฤฑlarฤฑn katlarฤฑnฤฑ iลaretleyin. Bu adฤฑm O( ) gerektirir.) maksimum dรผzeyde.
Normal elek O(n) yardฤฑmcฤฑ bellek alanฤฑna ihtiyaรง duyarken, bรถlรผmlรผ elek O(Bu, bรผyรผk bir n iรงin รถnemli bir iyileลmedir. Ancak yรถntemin bir dezavantajฤฑ da vardฤฑr, รงรผnkรผ zaman karmaลฤฑklฤฑฤฤฑnฤฑ iyileลtirmez.
Karmaลฤฑklฤฑk Analizi
Hem alan hem de zaman karmaลฤฑklฤฑฤฤฑnฤฑ anlamak, belirli bir problem boyutu iรงin normal elek yรถntemi ile bรถlรผmlรผ elek yรถntemi arasฤฑnda seรงim yapmanฤฑza yardฤฑmcฤฑ olur.
Uzay Karmaลฤฑklฤฑฤฤฑ:
Basit Eratosthenes Kalburu algoritmasฤฑ O(n) bellek alanฤฑ gerektirir. Bรถlรผmlรผ kalbur ise O() yardฤฑmcฤฑ alan.
Zaman Karmaลฤฑklฤฑฤฤฑ:
Normal bir Eratosthenes Kalburu algoritmasฤฑnฤฑn zaman karmaลฤฑklฤฑฤฤฑ O(n*log(log(n)))'dir. Bu karmaลฤฑklฤฑฤฤฑn ardฤฑndaki mantฤฑk aลaฤฤฑda tartฤฑลฤฑlmaktadฤฑr.
Verilen bir n sayฤฑsฤฑ iรงin, bileลik bir sayฤฑyฤฑ (yani asal olmayan bir sayฤฑyฤฑ) iลaretlemek iรงin gereken sรผre sabittir. Dolayฤฑsฤฑyla, dรถngรผnรผn รงalฤฑลma sayฤฑsฤฑ ลuna eลittir:
n/2 + n/3 + n/5 + n/7 + โฆโฆโ
= n * (1/2 + 1/3 + 1/5 + 1/7 +โฆโฆ.โ)
Asal sayฤฑlarฤฑn toplamฤฑnฤฑn harmonik dizisi log(log(n)) olarak รงฤฑkarฤฑlabilir:
(1/2 + 1/3 + 1/5 + 1/7 +โฆโฆ.โ) = log(log(n))
Dolayฤฑsฤฑyla, zaman karmaลฤฑklฤฑฤฤฑ ลu ลekilde olacaktฤฑr:
T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + โฆโฆโ)
= n * log(log(n))
Dolayฤฑsฤฑyla zaman karmaลฤฑklฤฑฤฤฑ O(n * log(log(n)))'dir.
Sonraki bรถlรผmde ลunlarฤฑ รถฤreneceksiniz: Pascal รรงgeni.
