Sito Eratostenesa

Zadanie 1. „Napisz program, który za pomocą sita Eratostenesa znajdzie wszystkie liczby pierwsze w zadanym przedziale [a, b].”
Dane wejściowe:
odczytać dane (np. a=20, b=65),

---

Etapy rozwiązania

1. Określenie zakresu

Chcemy liczby pierwsze od 20 do 65.
Ale sito zawsze startuje od 2, więc tworzymy tablicę od 2 do 65.
Zasada działania sita

Tak aż do pierwiastka z 65 (około 8).
Tworzymy listę, gdzie zakładamy, że każda liczba jest pierwsza.
Zaczynamy od 2. Skreślamy jej wielokrotności (4, 6, 8…).
Potem 3 – skreślamy wielokrotności (6, 9, 12…).
Następnie 5 – skreślamy (10, 15, 20…).

Algorytm – sito Eratostenesa (dla zakresu 20–65)

Wejście: liczba górna zakresu n = 65
Wyjście: liczby pierwsze w zakresie od 20 do 65

Kroki:

1. Przyjmij liczbę n = 65.
2. Utwórz tablicę pierwsze o rozmiarze n+1, wypełnioną wartościami True.
3. Ustaw pierwsze[0] oraz pierwsze[1] na False, ponieważ 0 i 1 nie są liczbami pierwszymi.
4. Dla każdej liczby p od 2 do √n: a. Jeśli pierwsze[p] == True, to: b. Skreśl (ustaw na False) wszystkie wielokrotności liczby p, począwszy od p * p.
5. Po zakończeniu działania sita tablica pierwsze zawiera informację, które liczby są pierwsze w całym zakresie od 2 do 65.
6. Wypisz tylko te liczby i, dla których pierwsze[i] == True i 20 ≤ i ≤ 65.

---

Rezultat działania:

Liczby pierwsze w zakresie 20–65 to:
23, 29, 31, 37, 41, 43, 47, 53, 59, 61.

---

Kod w Pythonie

def sito_eratostenesa(n):
    # Tworzymy listę wartości True (prawda), czyli zakładamy, że wszystkie liczby są pierwsze
    pierwsze = [True] * (n + 1)
    pierwsze[0] = pierwsze[1] = False  # 0 i 1 nie są pierwsze

    # Przechodzimy po liczbach do pierwiastka z n
    p = 2
    while p * p <= n:
        if pierwsze[p]:
            # Skreślamy wszystkie wielokrotności liczby p
            for i in range(p * p, n + 1, p):
                pierwsze[i] = False
        p += 1

    return pierwsze

# Szukamy liczb pierwszych do 65
n = 65
pierwsze = sito_eratostenesa(n)

# Wypisujemy tylko te z zakresu 20–65
print("Liczby pierwsze w zakresie 20–65:")
for i in range(20, n + 1):
    if pierwsze[i]:
        print(i, end=" ")

Opis kodu

1. pierwsze = [True] * (n + 1) Tworzymy listę długości n+1, gdzie zakładamy, że wszystkie liczby są pierwsze.
2. pierwsze[0] = pierwsze[1] = False Ustawiamy, że 0 i 1 nie są pierwsze.
3. Pętla while p * p <= n: Sprawdzamy kolejne liczby p. Wystarczy iść tylko do pierwiastka z n, bo większe i tak będą wielokrotnościami mniejszych.
4. for i in range(p * p, n + 1, p): Skreślamy wielokrotności liczby p, zaczynając od p*p (bo mniejsze wielokrotności już były skreślone).
5. Wypisywanie wyników: Iterujemy od 20 do 65 i pokazujemy tylko te, które zostały oznaczone jako pierwsze (True).