0Pricing
Coding Interview Prep · Lekcja

Sito Eratostenesa

Wypisywanie wszystkich liczb pierwszych do N w czasie niemal liniowym

Sito Eratostenesa to bezpłatna lekcja Coding Interview Prep 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 Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep 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 Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Sito Eratostenesa”?

Wypisywanie wszystkich liczb pierwszych do N w czasie niemal liniowym Ćwiczysz Coding Interview Prep 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ąć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep 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 Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep 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 Coding Interview Prep