Szybki sposób na znalezienie wszystkich liczb pierwszych do n przez wykreślanie wielokrotności.
Sito Eratostenesa to szybki sposób na znalezienie wszystkich liczb pierwszych aż do wybranej liczby n. Nazwa pochodzi od greckiego uczonego Eratostenesa, który wymyślił tę metodę ponad dwa tysiące lat temu.
Jak to działa? Wypisujemy wszystkie liczby od 2 do n. Bierzemy pierwszą z nich – dwójkę. Jest pierwsza, więc ją zostawiamy, ale wykreślamy wszystkie jej wielokrotności (4, 6, 8, …), bo skoro dzielą się przez 2, na pewno nie są pierwsze. Potem przechodzimy do następnej niewykreślonej liczby (trójki) i znów wykreślamy jej wielokrotności. Robimy tak dalej. Liczby, które na końcu zostały niewykreślone, to właśnie liczby pierwsze.
Skąd nazwa „sito"? Bo to działa jak przesiewanie: liczby złożone „wypadają" przez sito, a zostają tylko pierwsze.
Mały skrót. Wykreślanie wielokrotności liczby i można zacząć dopiero od i · i. Mniejsze wielokrotności zostały już wcześniej wykreślone przez mniejsze liczby (np. 10 i 15 skreśliły już dwójka i trójka, zanim doszliśmy do piątki).
Na maturze: sito przydaje się, gdy trzeba szybko sprawdzić pierwszość wielu liczb naraz albo wypisać wszystkie liczby pierwsze z jakiegoś zakresu.
Zobacz, jak sito „przesiewa" liczby od 2 do 30. W każdym kroku bierzemy najmniejszą liczbę bez skreślenia – jest pierwsza (na zielono) – i wykreślamy wszystkie jej wielokrotności. Na końcu zielone liczby to wszystkie liczby pierwsze.
Naciśnij „Krok", aby wziąć pierwszą liczbę pierwszą, albo „Auto".
funkcja sito(n): 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 // wykreślamy wielokrotność j ← j + i zwróć czy_pierwsza
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]]
# Przyklad uzycia
print(sito_eratostenesa(30))
# 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; // wykreślamy wielokrotność
}
}
vector<int> wynik;
for (int i = 2; i <= n; i++)
if (czy_pierwsza[i]) wynik.push_back(i);
return wynik;
}
int main() {
for (int x : sito_eratostenesa(30)) cout << x << " ";
// Wynik: 2 3 5 7 11 13 17 19 23 29
}Bo mniejsze wielokrotności zostały już wcześniej wykreślone przez mniejsze liczby. Na przykład zanim dojdziemy do piątki, liczby 10 i 15 skreśliły już dwójka i trójka. Start od i · i oszczędza tę powtórkę.
Bo zamiast dla każdej liczby osobno szukać dzielników, raz przechodzimy listę i skreślamy wielokrotności „hurtem". Gdy liczb jest dużo, to ogromna oszczędność czasu.
Wykreślać wielokrotności trzeba tylko dla liczb do pierwiastka z n. Jeśli liczba przetrwała do tego momentu, jest już pierwsza.
Wszędzie tam, gdzie potrzebujesz od razu wielu liczb pierwszych – na przykład w zadaniach, w których wiele razy sprawdzasz, czy liczba jest pierwsza.
Uzupełnij i kliknij Sprawdź.
Liczby pierwsze do 10 to: 2, 3, 5, . Najmniejsza liczba pierwsza to . Czy liczba 1 jest pierwsza? Wpisz tak lub nie: .
Policz, ile jest liczb pierwszych w danym zakresie:
| Zakres | Ile liczb pierwszych |
|---|---|
| do 10 | |
| do 20 | |
| do 30 |
O(n log log n)O(n)Sito jest bardzo szybkie – działa w czasie prawie liniowym względem n (zapisujemy to jako O(n log log n), co w praktyce jest tylko odrobinę wolniejsze od O(n)). Zajmuje za to O(n) pamięci, bo dla każdej liczby od 0 do n trzyma znacznik: pierwsza czy nie.
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: