Algorytm Sito Eratostenesa jest klasycznym algorytmem do znajdowania wszystkich liczb pierwszych mniejszych niż pewna dana liczba n. Działa on w sposób iteracyjny, eliminując wielokrotności liczb pierwszych, aż do pozostawienia wyłącznie liczb pierwszych.
Kroki działania algorytmu Sito Eratostenesa
1. Inicjalizacja
Tworzymy listę liczby o długości n+1 (ponieważ sprawdzamy liczby od 0 do n), w której każda pozycja początkowo przyjmuje wartość True. Pozycja i w tej liście będzie oznaczała, czy liczba i jest liczbą pierwszą.
Ustawiamy liczby[0] i liczby[1] na False, ponieważ 0 i 1 nie są liczbami pierwszymi.
2. Iteracja przez liczby
Przechodzimy przez listę liczby zaczynając od liczby 2, czyli pierwszej liczby pierwszej.
Dla każdej liczby i, która ma wartość True w liście liczby, oznacza to, że i jest liczbą pierwszą. Następnie usuwamy (czyli ustawiamy na False) wszystkie wielokrotności tej liczby i zaczynając od i * i (ponieważ mniejsze wielokrotności i zostały już usunięte przez wcześniejsze liczby pierwsze).
3. Usuwanie wielokrotności
Jeśli i jest liczbą pierwszą, usuwamy wszystkie liczby w postaci i * i, i * (i + 1), i * (i + 2), ..., aż do n. Proces ten powtarzamy dla każdej liczby do pierwiastek(n), ponieważ każda liczba większa niż pierwiastek(n), która nie jest wielokrotnością żadnej liczby mniejszej lub równej pierwiastek(n) musi być liczbą pierwszą.
4. Zbieranie wyników
Po zakończeniu iteracji wszystkie liczby, które mają wartość True w liście liczby, są liczbami pierwszymi.
Przykład działania sita Eratostenesa
np. dla n=30
Tworzymy listę liczb od 0 do 30:
liczby = [False, False, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True]
Zaczynamy od i = 2
2 jest liczbą pierwszą, więc usuwamy wszystkie jej wielokrotności większe od 2, czyli 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.
Lista po tej operacjiliczby = [False, False, True, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False]
Następnie i = 3
3 jest liczbą pierwszą, więc usuwamy wszystkie jego wielokrotności większe od 3, czyli 9, 12, 15, 18, 21, 24, 27, 30.Lista po tej operacji
liczby = [False, False, True, True, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False]
Następnie i = 4
4 jest już oznaczone jako False (usunięte), więc przechodzimy dalej.
Następnie i = 5
5 jest liczbą pierwszą, więc usuwamy wszystkie jego wielokrotności większe od 5, czyli 25, 30.
Lista po tej operacjiliczby = [False, False, True, True, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False, False, False, False, False, True, False]
Kontynuujemy ten proces do liczby nie większej niż pierwiastek z 30 (około 5,47), czyli w ww. przypadku do liczby 5 (co już zrealizowano), a następnie zbieramy wszystkie liczby oznaczone jako True.
Zatem wynik (liczby pierwsze do 30) to [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Złożoność obliczeniowa
Algorytm Sito Eratostenesa ma nietypową złożoność czasową O(n loglogn) i złożoność pamięciową O(n), co czyni go bardzo efektywnym dla dużych wartości n.
Sito Eratostenesa w języku Python
dla n=30 (deklaracja na końcu kodu)
def sito_eratostenesa(n):
# Tworzymy listę prawda/fałsz dla wszystkich liczb od 0 do n
liczby = [True] * (n + 1)
liczby[0] = liczby[1] = False # 0 i 1 nie są liczbami pierwszymi
# Rozpoczynamy sito
for i in range(2, int(n**0.5) + 1):
if liczby[i]: # Jeśli liczba jest pierwsza
# Usuwamy wszystkie jej wielokrotności
for j in range(i * i, n + 1, i):
liczby[j] = False
# Zwracamy wszystkie liczby, które pozostały jako prawda (czyli liczby pierwsze)
return [i for i in range(n + 1) if liczby[i]]
# Przykład użycia
print(sito_eratostenesa(30))
Sito Eratostenesa w języku C++
#include <iostream>
#include <vector>
std::vector<int> sito_eratostenesa(int n) {
std::vector<bool> liczby(n + 1, true);
liczby[0] = liczby[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (liczby[i]) {
for (int j = i * i; j <= n; j += i) {
liczby[j] = false;
}
}
}
std::vector<int> primes;
for (int i = 2; i <= n; ++i) {
if (liczby[i]) {
primes.push_back(i);
}
}
return primes;
}
int main() {
int n = 30;
std::vector<int> primes = sito_eratostenesa(n);
for (int prime : primes) {
std::cout << prime << " ";
}
return 0;
}
Sito Eratostenesa w języku Java
import java.util.ArrayList;
import java.util.List;
public class SitoEratostenesa {
public static List<Integer> sitoEratostenesa(int n) {
boolean[] liczby = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
liczby[i] = true;
}
for (int i = 2; i * i <= n; i++) {
if (liczby[i]) {
for (int j = i * i; j <= n; j += i) {
liczby[j] = false;
}
}
}
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (liczby[i]) {
primes.add(i);
}
}
return primes;
}
public static void main(String[] args) {
int n = 30;
List<Integer> primes = sitoEratostenesa(n);
System.out.println(primes);
}
}
Sito Eratostenesa w języku JavaScript
function sitoEratostenesa(n) {
let liczby = Array(n + 1).fill(true);
liczby[0] = liczby[1] = false;
for (let i = 2; i * i <= n; i++) {
if (liczby[i]) {
for (let j = i * i; j <= n; j += i) {
liczby[j] = false;
}
}
}
let primes = [];
for (let i = 2; i <= n; i++) {
if (liczby[i]) {
primes.push(i);
}
}
return primes;
}
let n = 30;
console.log(sitoEratostenesa(n));Sito Eratostenesa w języku PHP
<?php
function sitoEratostenesa($n) {
$liczby = array_fill(0, $n + 1, true);
$liczby[0] = $liczby[1] = false;
for ($i = 2; $i * $i <= $n; $i++) {
if ($liczby[$i]) {
for ($j = $i * $i; $j <= $n; $j += $i) {
$liczby[$j] = false;
}
}
}
$primes = [];
for ($i = 2; $i <= $n; $i++) {
if ($liczby[$i]) {
$primes[] = $i;
}
}
return $primes;
}
$n = 30;
$primes = sitoEratostenesa($n);
echo implode(", ", $primes);
?>
Komentarze