Sito Eratostenesa do 50

Liczby pierwsze i sito Eratostenesa - Algorytmy z podstawy programowej (Python)

Gdy potrzebujemy **wszystkich** liczb pierwszych do pewnej granicy, szybsze jest sito Eratostenesa. Zaczynamy od listy, w której każda liczba jest "kandydatem". Bierzemy najmniejszą niewykreśloną liczbę p i wykreślamy jej wielokrotności (od p * p, bo mniejsze wykreśliły już mniejsze liczby). Co zostaje, jest pierwsze. Krokuj i obserwuj listę `pierwsza` w podglądzie zmiennych.

N = 50
pierwsza = [True] * (N + 1)
pierwsza[0] = pierwsza[1] = False
p = 2
while p * p <= N:
    if pierwsza[p]:
        for k in range(p * p, N + 1, p):
            pierwsza[k] = False
    p += 1

wynik = [i for i in range(N + 1) if pierwsza[i]]
print(wynik)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy z podstawy programowej·Zaloguj się, aby zapisać postęp na koncie.