0Pricing
Competitive Programming Academy · Lekcja

Sito Eratostenesa

Wypisywanie wszystkich liczb pierwszych do N w czasie niemal liniowym

Sito Eratostenesa to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.

Liczby pierwsze hurtowo

Czasami potrzebne są wszystkie liczby pierwsze do N, a nie tylko pojedyncze sprawdzenie. Sito Eratostenesa znajduje je wszystkie w jednym przejściu. 🧹

Najważniejsza idea

Najpierw należy założyć, że każda liczba jest pierwsza. Następnie trzeba wykreślać wielokrotności każdej znalezionej liczby pierwszej, pozostawiając wyłącznie prawdziwe liczby pierwsze.

Przygotowanie znaczników

Należy utworzyć listę wartości logicznych, w której indeks i oznacza, czy i jest liczbą pierwszą. Ta tablica jest obszarem roboczym, na którym działa sito.

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

Przechodzenie po kandydatach

Należy przechodzić po kolejnych wartościach i. Gdy po raz pierwszy napotkamy liczbę, dla której nadal ustawiono True, musi to być nowa liczba pierwsza bez mniejszego czynnika.

Wykreślanie wielokrotności

Dla każdej liczby pierwszej i należy oznaczyć 2i, 3i, 4i i tak dalej jako liczby niepierwsze. Te wielokrotności mają i jako dzielnik.

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

Rozpoczęcie od i do kwadratu

Wykreślanie należy rozpocząć od i*i, a nie od 2i. Każda mniejsza wielokrotność została już usunięta przez wcześniejszą liczbę pierwszą, więc można ją pominąć.

Zatrzymanie na pierwiastku

Wystarczy wykonywać sito, dopóki i*i pozostaje mniejsze lub równe N. Powyżej pierwiastka kwadratowego każda pozostała wartość True jest już liczbą pierwszą.

Pełne sito

Należy połączyć zewnętrzne przejście ze skreślaniem w pętli wewnętrznej. Po zakończeniu pętli każdy indeks, dla którego nadal ustawiono True, oznacza potwierdzoną liczbę pierwszą.

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

Zbieranie liczb pierwszych

Należy odczytać gotowe znaczniki do listy za pomocą składni list comprehension. Teraz dostępne są wszystkie liczby pierwsze do N, gotowe do szybkich zapytań.

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

Dlaczego to działa szybko

Sito działa w czasie około O(n log log n), czyli niemal liniowym. Dlatego zdecydowanie przewyższa wielokrotne sprawdzanie pojedynczych liczb.

Uwaga na pamięć

Tablica znaczników zajmuje pamięć proporcjonalną do N. Dla bardzo dużych limitów należy sprawdzić dostępny budżet pamięci przed alokacją.

Szybkie sprawdzenie

Proszę przypomnieć sobie małą optymalizację w pętli wewnętrznej.

Podsumowanie

Można już zbudować sito, aby wypisać wszystkie liczby pierwsze do N w niemal liniowym czasie, rozpoczynając wykreślanie każdej liczby pierwszej od i*i i zatrzymując się na pierwiastku. ✅

Często zadawane pytania

Czy lekcja „Sito Eratostenesa” jest bezpłatna?

Tak — pełny tekst „Sito Eratostenesa” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Sito Eratostenesa”?

Wypisywanie wszystkich liczb pierwszych do N w czasie niemal liniowym Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?

Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Sito Eratostenesa”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?

Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. NWD, NWW i algorytm Euklidesa
  2. Testowanie pierwszości do sqrt(n)
  3. Sito Eratostenesa
  4. Rozkład na czynniki pierwsze i dzielniki
← Powrót do Competitive Programming Academy