Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...
2den n değerine kadar asal sayıları, asal katlarını topluca eleyerek üreten klasik sayı teorisi algoritmasıdır.
Sieve of Eratosthenes, her adımda bulunan asal sayının katlarını composite olarak işaretler. Kritik optimizasyon, p asalına gelindiğinde işaretlemeye p * p değerinden başlamaktır; çünkü daha küçük katlar daha küçük asal çarpanlar tarafından zaten elenmiştir.
Bu yöntem tek tek adaylar için bölünebilirlik testi yapmaktan farklıdır: aralıktaki bileşik sayıları doğrudan üretir ve işaretlenmeden kalan değerler asal olur.
Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.
1function sieveOfEratosthenes(limit: number): number[] {2 const isPrime = Array(limit + 1).fill(true);3 isPrime[0] = false; isPrime[1] = false;4 for (let value = 2; value * value <= limit; value += 1) {5 if (!isPrime[value]) continue;6 for (let multiple = value * value; multiple <= limit; multiple += value) {7 isPrime[multiple] = false;8 }9 }10 return isPrime.map((prime, value) => (prime ? value : null)).filter((value): value is number => value !== null);11}Bir üst limit girin. Örnek: 100
Bir üst limit girin. Örnek: 100
En İyi Durum: O(n log log n)
Ortalama Durum: O(n log log n)
En Kötü Durum: O(n log log n)
O(n) - Çalışma süresi, giriş boyutu ile doğrusal olarak artar.
Sieve of Eratosthenes Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar: