Competitive Programming Academy · Ders

Eratosthenes Eleği

N'ye kadar tüm asalları neredeyse doğrusal zamanda listeleyin.

3. ders / 413 adım

Eratosthenes Eleği, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Competitive Programming Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Competitive Programming Academy kursu toplamda 4 dersten oluşur.

Toplu Asal Sayılar

Bazen yalnızca tek bir sayıyı sınamak değil, N'ye kadar olan tüm asal sayıları bulmak gerekir. Eratosthenes Eleği hepsini tek bir taramada bulur. 🧹

Temel Fikir

Önce her sayının asal olduğunu varsayın. Ardından bulduğunuz her asalın katlarını eleyin; geriye yalnızca gerçek asallar kalsın.

İşaretleri Ayarlayın

i indisinin asal olup olmadığını belirten bir mantıksal liste oluşturun. Bu dizi, eleğin üzerinde işlem yaptığı alandır.

is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False

Adayları Tarayın

i'yi artırarak ilerleyin. Hâlâ True olarak işaretlenmiş bir sayıya ilk ulaştığınızda, daha küçük bir çarpanı olmayan yeni bir asal bulmuş olursunuz.

Katları Eleyin

Her i asalı için 2i, 3i, 4i ve devamını asal değil olarak işaretleyin. Bu katların i'yi bölen olarak içerdiği açıktır.

for j in range(i * i, n + 1, i):
    is_prime[j] = False

i Kareden Başlayın

Elemeye 2i'den değil, i*i'den başlayın. Daha küçük tüm katlar daha önceki bir önceki asal tarafından zaten elenmiştir; bu nedenle onları atlayın.

Kökte Durun

Yalnızca i*i, N'den küçük veya N'ye eşit kaldığı sürece eleme yapmanız gerekir. Karekökün ötesinde, True olarak kalan her işaret zaten asaldır.

Tam Elek

Dış taramayı ve iç eleme işlemini birleştirin. Döngüden sonra True olarak işaretlenmiş her indis doğrulanmış bir asaldır.

for i in range(2, int(n ** 0.5) + 1):
    if is_prime[i]:
        for j in range(i * i, n + 1, i):
            is_prime[j] = False

Asalları Toplayın

Tamamlanmış işaretleri bir liste üreteciyle bir listeye aktarın. Artık N'ye kadar olan tüm asal sayılar hızlı sorgular için elinizdedir.

primes = [i for i, p in enumerate(is_prime) if p]

Neden Hızlıdır

Elek yaklaşık O(n log log n) zamanda, yani neredeyse doğrusal sürede çalışır. Tek sayıları tekrar tekrar sınamayı bu nedenle geride bırakır.

Belleği Göz Önünde Bulundurun

İşaret dizisi, N ile orantılı miktarda bellek kullanır. Çok büyük sınırlar için yer ayırmadan önce bellek bütçenizi kontrol edin.

Hızlı Kontrol

İç döngüdeki küçük iyileştirmeyi hatırlayın.

İnteraktif derste cevapla

Özet

Artık N'ye kadar olan tüm asalları neredeyse doğrusal zamanda listelemek için bir elek oluşturabilir, her asalı i*i'den başlatabilir ve kökte durabilirsiniz. ✅

Başlamak ücretsiz

Yapay zeka eğitmeniyle Python öğren — ücretsiz

Tarayıcında gerçek kod yaz ve çalıştır, 7/24 yapay zeka eğitmeninden anında yardım al; web'de ya da uygulamada kaldığın yerden devam et.

Kurslar: 30
Dersler: 120

Ücretsiz öğrenmeye başla Tüm kursu görüntüle

Sıkça Sorulan Sorular

“Eratosthenes Eleği” dersi ücretsiz mi?

Evet — “Eratosthenes Eleği” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Competitive Programming Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Competitive Programming Academy kursu toplamda 4 dersten oluşur.

“Eratosthenes Eleği” dersinde ne öğreneceğim?

N'ye kadar tüm asalları neredeyse doğrusal zamanda listeleyin. Competitive Programming Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.

Competitive Programming Academy öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Competitive Programming Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.

“Eratosthenes Eleği” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Bu Competitive Programming Academy dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Competitive Programming Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Bu kursun tüm dersleri

← Competitive Programming Academy Sayfasına Dön