Algoritam Eratostenovog sita: Python, C++ Primjer
Eratostenovo sito je najjednostavnije sito prostih brojeva. To je algoritam prostih brojeva za pretraživanje svih prostih brojeva u zadanoj granici. Postoji nekoliko sita prostih brojeva. Na primjer, Eratostenovo sito, Atkinovo sito, Sundaramovo sito itd.
Riječ "sito” znači posuđe koje filtrira tvari. Dakle, algoritam sita u Python i drugim jezicima odnosi se na algoritam za filtriranje prostih brojeva.
Ovaj algoritam filtrira primarni broj u iterativnom pristupu. Proces filtriranja počinje s najmanjim prostim brojem. Prosti je prirodni broj koji je veći od 1 i ima samo dva djelitelja, naime 1 i sam broj. Brojevi koji nisu prosti nazivaju se složeni brojevi.
U situ Eratostenove metode prvo se odabire mali prosti broj, a svi njegovi višekratnici se filtriraju. Proces se izvodi u petlji u zadanom rasponu.
Na primjer:
Uzmimo raspon brojeva od 2 do 10.
Nakon primjene Eratostenovog sita, proizvest će popis prostih brojeva 2, 3, 5, 7
Eratostenovo sito algoritma
Ovo je algoritam za Eratostenovo sito:
Korak 1) Napravite popis brojeva od 2 do zadanog raspona n. Počinjemo s 2 jer je to najmanji i prvi prosti broj.
Korak 2) Odaberite najmanji broj na popisu, x (u početku je x jednako 2), prođite kroz popis i filtrirajte odgovarajuće složene brojeve označavajući sve višekratnike odabranih brojeva.
Korak 3) Zatim odaberite sljedeći prosti ili najmanji neoznačeni broj na popisu i ponovite korak 2.
Korak 4) Ponavljajte prethodni korak sve dok vrijednost x ne bude manja ili jednaka kvadratnom korijenu iz n (x<=).
Bilješka: Matematičko razmišljanje je vrlo jednostavno. Raspon brojeva n može se faktorizirati kao
n=a*b
Opet, n =*
= (faktor manji od ) * (faktor veći od
)
Dakle, barem jedan od glavni faktori ili oba moraju biti <=. Dakle, prelazeći na
bit će dovoljno.
Korak 5) Nakon ta četiri koraka, preostali neoznačeni brojevi bili bi svi prosti brojevi u danom rasponu n.
Primjer:
Uzmimo primjer i vidimo kako funkcionira.
Za ovaj primjer, pronaći ćemo popis prostih brojeva od 2 do 25. Dakle, n=25.
Korak 1) U prvom koraku uzet ćemo popis brojeva od 2 do 25 jer smo odabrali n=25.
Korak 2) Zatim odabiremo najmanji broj na listi, x. U početku x=2 jer je to najmanji prosti broj. Zatim prelazimo kroz popis i označavamo višekratnike 2.
Višekratnici broja 2 za danu vrijednost n su: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.
Bilješka: Plava boja označava odabrani broj, a ružičasta boja označava eliminirane višekratnike
Korak 3) Zatim biramo sljedeći najmanji neoznačeni broj, a to je 3, i ponavljamo zadnji korak označavajući višekratnike broja 3.
Korak 4) Ponavljamo korak 3 na isti način dok x= ili 5.
Korak 5) Preostali neoznačeni brojevi bili bi prosti brojevi od 2 do 25.
Pseudo-kod
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
Eratostenovo sito C/C++ primjer koda
#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; }
Izlaz:
2 3 5 7 11 13 17 19 23
Sita Eratostena Python Primjer programa
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)
Izlaz:
2 3 5 7 11 13 17 19 23
Segmentirano sito
Vidjeli smo da je Eratostenovo sito potrebno za pokretanje petlje kroz čitav raspon brojeva. Stoga mu je potrebno O(n) memorijskog prostora za pohranjivanje brojeva. Situacija postaje komplicirana kada pokušavamo pronaći proste brojeve u velikom rasponu. Nije moguće dodijeliti tako velik memorijski prostor za veći n.
Algoritam se može optimizirati uvođenjem nekih novih značajki. Ideja je podijeliti raspon brojeva u manje segmente i izračunati proste brojeve u tim segmentima jedan po jedan. Ovo je učinkovit način smanjenja složenosti prostora. Ova metoda se naziva a segmentirano sito.
Optimizacija se može postići na sljedeći način:
- Pomoću jednostavnog sita pronađite proste brojeve od 2 do
i pohraniti ih u niz.
- Podijelite raspon [0…n-1] u više segmenata najviše veličine
- Za svaki segment, iterirajte kroz segment i označite višekratnik prostih brojeva pronađenih u koraku 1. Ovaj korak zahtijeva O(
) na maks.
Redovno sito zahtijeva O(n) pomoćnog memorijskog prostora, dok segmentirano sito zahtijeva O(), što je veliki napredak za veliki n. Metoda ima i lošu stranu jer ne poboljšava vremensku složenost.
Analiza složenosti
Složenost prostora:
Jednostavno sito Eratostenovog algoritma zahtijeva O(n) memorijskog prostora. I segmentirano sito zahtijeva
O() pomoćni prostor.
Složenost vremena:
Vremenska složenost regularnog sita Eratostenovog algoritma je O(n*log(log(n))). Razlozi za ovu složenost razmatraju se u nastavku.
Za zadani broj n, vrijeme potrebno za označavanje složenog broja (tj. neprostih brojeva) je konstantno. Dakle, broj pokretanja petlje jednak je-
n/2 + n/3 + n/5 + n/7 + ……∞
= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)
Harmonijska progresija zbroja prostih brojeva može se oduzeti kao log(log(n)).
(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))
Dakle, vremenska složenost će biti-
T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)
= n * log(log(n))
Dakle, vremenska složenost O(n * log(log(n)))
Zatim ćete naučiti o Pascalov trokut
rezime
- Eratostenovo sito filtrira proste brojeve u zadanoj gornjoj granici.
- Filtriranje prostog broja počinje od najmanjeg prostog broja, "2". Ovo se radi iterativno.
- Iteracija se provodi do kvadratnog korijena iz n, gdje je n zadani raspon brojeva.
- Nakon ovih ponavljanja, brojevi koji ostaju su prosti brojevi.