Sito Eratostenesa - Generowanie Liczb Pierwszych na Maturze

def sito(n):
    """Generuje sito Eratostenesa do liczby n."""
    # 1. Stwórz tablicę i zainicjuj ją jako True
    is_prime = [True] * (n + 1)

    # 2. 0 i 1 nie są pierwsze
    is_prime[0] = is_prime[1] = False

    # 3. Pętla zewnętrzna do √n
    for p in range(2, int(n**0.5) + 1):
        # 4. Jeśli p jest pierwsze (nie zostało wykreślone)
        if is_prime[p]:
            # 5. Wykreśl wielokrotności p, zaczynając od p*p
            for i in range(p * p, n + 1, p):
                is_prime[i] = False

    # Opcjonalnie: Zwróć listę liczb pierwszych
    primes = []
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)

    return is_prime, primes

# Przykład użycia do znalezienia liczb pierwszych do 30
is_prime_do_30, primes_do_30 = sito(30)
print(f"Liczby pierwsze do 30: {primes_do_30}")
print(f"Czy 17 jest pierwsza? {is_prime_do_30[17]}")
print(f"Czy 18 jest pierwsza? {is_prime_do_30[18]}")

To jest klasyczna, zoptymalizowana implementacja sita. Pętla zewnętrzna 'for p...' idzie tylko do pierwiastka z 'n' (√n). Pętla wewnętrzna 'for i...' zaczyna wykreślanie od 'p*p', ponieważ wszystkie mniejsze wielokrotności (jak 2*p, 3*p) zostały już wykreślone przez mniejsze liczby pierwsze.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<bool> sito(int n) {
    // 1. Stwórz wektor i zainicjuj go jako true
    vector<bool> is_prime(n + 1, true);

    // 2. 0 i 1 nie są pierwsze
    is_prime[0] = is_prime[1] = false;

    // 3. Pętla zewnętrzna do √n
    for (int p = 2; p * p <= n; p++) {
        // 4. Jeśli p jest pierwsze
        if (is_prime[p]) {
            // 5. Wykreśl wielokrotności p, zaczynając od p*p
            for (int i = p * p; i <= n; i += p)
                is_prime[i] = false;
        }
    }
    return is_prime;
}

int main() {
    int n = 30;
    vector<bool> is_prime_do_30 = sito(n);

    cout << "Liczby pierwsze do 30: ";
    for (int i = 2; i <= n; i++) {
        if (is_prime_do_30[i]) {
            cout << i << " ";
        }
    }
    cout << endl;
    cout << "Czy 17 jest pierwsza? " << is_prime_do_30[17] << endl; // Wypisze 1 (true)
    cout << "Czy 18 jest pierwsza? " << is_prime_do_30[18] << endl; // Wypisze 0 (false)
    return 0;
}

Logika jest identyczna jak w Pythonie. Używamy `vector<bool>`, który jest wydajną implementacją tablicy logicznej w C++. Zamiast `int(n**0.5) + 1` możemy użyć wydajniejszego warunku w pętli: `p * p <= n`.