Síto of Eratosthenes algoritmus: Python, C++ Příklad
Sarah Chen
Eratosthenovo síto je nejjednodušší prvočíselné síto. Je to algoritmus prvočísel, který prohledává všechna prvočísla v daném limitu. Existuje několik prvočíselných sít. Například - Eratosthenovo síto, Atkinovo síto, Sundaramské síto atd.
Slovo "síto“ znamená nádobu, která filtruje látky. Algoritmus síta je tedy v Python a další jazyky odkazuje na algoritmus pro filtrování prvočísel.
Tento algoritmus filtruje prvočíslo v iterativním přístupu. Proces filtrování začíná nejmenším prvočíslem. Prvočíslo je přirozené číslo, které je větší než 1 a má pouze dva dělitele, tj. 1 a samotné číslo. Čísla, která nejsou prvočísla, se nazývají složená čísla.
V sítu Eratosthenovy metody se nejprve vybere malé prvočíslo a všechny jeho násobky se odfiltrují. Proces běží na smyčce v daném rozsahu.
Například:
Vezměme rozsah čísel od 2 do 10.
Po použití Eratosthenova síta vytvoří seznam prvočísel 2, 3, 5, 7
Algoritmus Eratosthenova síta
Zde je algoritmus pro Eratosthenovo síto:
Krok 1) Vytvořte seznam čísel od 2 do daného rozsahu n. Začneme 2, protože je to nejmenší a první prvočíslo.
Krok 2) Vyberte nejmenší číslo v seznamu, x (zpočátku se x rovná 2), procházejte seznam a filtrujte odpovídající složená čísla označením všech násobků vybraných čísel.
Krok 3) Poté vyberte další prvočíslo nebo nejmenší neoznačené číslo v seznamu a opakujte krok 2.
Krok 4) Opakujte předchozí krok, dokud hodnota x nebude menší nebo rovna druhé odmocnině z n (x<=
).
Poznámka: Matematická úvaha je celkem jednoduchá. Číselný rozsah n lze faktorizovat jako-
n=a*b
Opět n =*
= (faktor menší než ) * (faktor větší než )
Tedy alespoň jeden z hlavní faktory nebo obojí musí být <=. Tedy přecházení do bude stačit.
Krok 5) Po těchto čtyřech krocích budou zbývající neoznačená čísla všechna prvočísla v daném rozsahu n.
Příklad:
Vezměme si příklad a uvidíme, jak to funguje.
Pro tento příklad najdeme seznam prvočísel od 2 do 25. Tedy n=25.
Krok 1) V prvním kroku si vezmeme seznam čísel od 2 do 25, protože jsme vybrali n=25.
Krok 2) Potom vybereme nejmenší číslo ze seznamu, x. Zpočátku x = 2, protože je to nejmenší prvočíslo. Poté procházíme seznamem a označíme násobky 2.
Násobky 2 pro danou hodnotu n jsou: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.
Poznámka: Modrá barva označuje vybrané číslo a růžová barva označuje vyřazené násobky
Krok 3) Poté zvolíme další nejmenší neoznačené číslo, což je 3, a poslední krok zopakujeme označením násobků 3.
Krok 4) Krok 3 opakujeme stejným způsobem až do x=
nebo 5.
Krok 5) Zbývající neoznačená čísla budou prvočísla od 2 do 25.
Pseudo kód
Begin
Declare a boolean array of size n and initialize it to true
For all numbers i : from 2 to sqrt(n)
IF bool value of i is true THEN
i is prime
For all multiples of i (i<n)
mark multiples of i as composite
Print all unmarked numbers
End
Síto Eratosthenes C/C++ Příklad kódu
#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
// Create and initialize a boolean array
bool primeNumber[n + 1];
memset(primeNumber, true, sizeof(primeNumber));
for (int j = 2; j * j <= n; j++) {
if (primeNumber[j] == true) {
// Update all multiples of i as false
for (int k = j * j; k <= n; k += j)
primeNumber[k] = false;
}
}
for (int i = 2; i <= n; i++)
if (primeNumber[i])
cout << i << " ";
}
int main()
{
int n = 25;
Sieve_Of_Eratosthenes(n);
return 0;
}
Výstup:
2 3 5 7 11 13 17 19 23
Síto Eratosthenes Python Příklad programu
def SieveOfEratosthenes(n): # Create a boolean array primeNumber = [True for i in range(n+2)] i = 2 while (i * i <= n): if (primeNumber[i] == True): # Update all multiples of i as false for j in range(i * i, n+1, i): primeNumber[j] = False i += 1 for i in range(2, n): if primeNumber[i]: print(i) n = 25 SieveOfEratosthenes(n)
Výstup:
2 3 5 7 11 13 17 19 23
Segmentované síto
Viděli jsme, že Eratosthenovo síto je nutné k proběhnutí smyčky přes celý číselný rozsah. K uložení čísel tedy potřebuje paměť O(n). Situace se komplikuje, když se snažíme najít prvočísla v obrovském rozsahu. Pro větší n není možné alokovat tak velký paměťový prostor.
Algoritmus lze optimalizovat zavedením některých nových funkcí. Cílem je rozdělit číselný rozsah na menší segmenty a vypočítat prvočísla v těchto segmentech jeden po druhém. Jedná se o efektivní způsob, jak snížit složitost prostoru. Tato metoda se nazývá a segmentované síto.
Optimalizace lze dosáhnout následujícím způsobem:
- Pomocí jednoduchého síta najděte prvočísla od 2 do a uložit je do pole.
- Rozdělte rozsah [0…n-1] maximálně na více segmentů velikosti
- Pro každý segment iterujte segment a označte násobek prvočísel nalezených v kroku 1. Tento krok vyžaduje O() při max.
Běžné síto vyžaduje O(n) pomocný paměťový prostor, zatímco segmentované síto vyžaduje O(), což je velké zlepšení pro velké n. Metoda má stinnou stránku také proto, že nezlepšuje časovou náročnost.
Analýza složitosti
Prostorová složitost:
Jednoduché síto eratosthenesova algoritmu vyžaduje O(n) paměťového prostoru. A segmentované síto vyžaduje
O() pomocný prostor.
Časová složitost:
Časová složitost pravidelného síta eratosthenova algoritmu je O(n*log(log(n))). Důvody této složitosti jsou diskutovány níže.
Pro dané číslo n je čas potřebný k označení složeného čísla (tj. neprvočísel) konstantní. Počet spuštění smyčky se tedy rovná -
n/2 + n/3 + n/5 + n/7 + ……∞
= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)
Harmonický průběh součtu prvočísel lze odečíst jako log(log(n)).
(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))
Takže časová složitost bude...
T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)
= n * log(log(n))
Tedy časová složitost O(n * log(log(n)))
Dále se dozvíte o Pascalův trojúhelník
Shrnutí
- Eratosthenovo síto odfiltruje prvočísla v dané horní hranici.
- Filtrování prvočísla začíná od nejmenšího prvočísla, „2“. To se provádí iterativně.
- Iterace se provádí až do druhé odmocniny z n, kde n je daný číselný rozsah.
- Po těchto iteracích jsou čísla, která zbývají, prvočísla.
