3.1 Sito Eratostenesa: idea

Matura próbna grudzień 2022 - Matura z informatyki: arkusze krok po kroku (Python)

**Zadanie 3. Liczby.** Sito Eratostenesa wyznacza wszystkie liczby pierwsze do \( N \): zaczyna od tablicy "wszystkie pierwsze", a potem dla kolejnej liczby pierwszej \( i \) skreśla jej wielokrotności. Program pokazuje, które liczby do 30 skreśla każde \( i \). Skreślanie zaczyna się od \( i \cdot i \): mniejsze wielokrotności (np. \( 3 \cdot 2 \)) skreśliła już mniejsza liczba pierwsza.

n = 30
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, n + 1):
    if is_prime[i] and i * i <= n:
        crossed = list(range(i * i, n + 1, i))
        for j in crossed:
            is_prime[j] = False
        print(i, "skreśla", crossed)
print("pierwsze:", [k for k in range(n + 1) if is_prime[k]])

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

Wszystkie lekcje kursu Matura z informatyki: arkusze krok po kroku·Zaloguj się, aby zapisać postęp na koncie.