średni liczby pierwszematura rozszerzona z informatyki

Sito Eratostenesa

Wyznacza wszystkie liczby pierwsze do n przez wykreślanie wielokrotności kolejnych liczb pierwszych.

Opis

Sito Eratostenesa to klasyczny algorytm wyznaczania wszystkich liczb pierwszych mniejszych lub równych zadanej liczbie n. Algorytm pochodzi od starożytnego greckiego matematyka Eratostenesa z Cyreny.

Idea działania: tworzymy listę kandydatów od 2 do n. Bierzemy najmniejszą niewykreśloną liczbę (zaczynamy od 2) i wykreślamy wszystkie jej wielokrotności. Powtarzamy dla kolejnych niewykreślonych liczb. Te, które pozostaną, są liczbami pierwszymi.

Zastosowanie w maturze: sito pojawia się w zadaniach na maturze rozszerzonej z informatyki, szczególnie gdy trzeba wielokrotnie sprawdzać czy liczba jest pierwsza w dużym zbiorze danych.

Pseudokod

funkcja sito(n):
  // tworzymy tablicę logiczną długości n+1
  dla i od 0 do n:
    czy_pierwsza[i] ← prawda
  czy_pierwsza[0] ← fałsz
  czy_pierwsza[1] ← fałsz

  dla i od 2 do √n:
    jeżeli czy_pierwsza[i] = prawda:
      j ← i * i
      dopóki j ≤ n:
        czy_pierwsza[j] ← fałsz
        j ← j + i

  zwróć czy_pierwsza

Implementacja w Pythonie i C++

def sito_eratostenesa(n):
    """Zwraca listę liczb pierwszych <= n."""
    if n < 2:
        return []

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

    for i in range(2, int(n ** 0.5) + 1):
        if czy_pierwsza[i]:
            # wykreślamy wielokrotności i, zaczynając od i*i
            for j in range(i * i, n + 1, i):
                czy_pierwsza[j] = False

    return [i for i in range(n + 1) if czy_pierwsza[i]]


# Przykład użycia
liczby_pierwsze = sito_eratostenesa(30)
print(liczby_pierwsze)
# Wynik: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

#include <vector>
#include <iostream>
using namespace std;

vector<int> sito_eratostenesa(int n) {
    if (n < 2) return {};
    vector<bool> czy_pierwsza(n + 1, true);
    czy_pierwsza[0] = czy_pierwsza[1] = false;

    for (int i = 2; (long long)i * i <= n; i++) {
        if (czy_pierwsza[i]) {
            for (int j = i * i; j <= n; j += i)
                czy_pierwsza[j] = false;
        }
    }

    vector<int> wynik;
    for (int i = 2; i <= n; i++)
        if (czy_pierwsza[i]) wynik.push_back(i);
    return wynik;
}

// Przykład użycia
int main() {
    auto liczby = sito_eratostenesa(30);
    for (int x : liczby) cout << x << " ";
    // Wynik: 2 3 5 7 11 13 17 19 23 29
}

Złożoność obliczeniowa

CzasowaO(n log log n)

PamięciowaO(n)

↗

Powiązane zagadnienia

Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem:

Rozkład na czynniki pierwszeLiczby Sprawdzanie liczby pierwszejLiczby Dzielniki liczbyLiczby Konwersja binarno-dziesiętnaLiczby Konwersja dziesiętno-binarnaLiczby NWD – algorytm EuklidesaLiczby