Eratostenovo sito u Python & C++

Što je Eratostenovo sito?

Eratostenovo sito je najjednostavnije sito prostih brojeva. To je algoritam za proste brojeve koji se koristi za otkrivanje svakog prostog broja unutar zadane granice. Postoji nekoliko prostih sita, uključujući Eratostenovo sito, Atkinovo sito i Sundaramovo sito.

Riječ "sito" odnosi se na pribor koji filtrira tvari. U istom duhu, algoritam sita u Python i drugi jezici odnose se na metodu koja filtrira proste brojeve iz popisa cijelih brojeva.

Ovaj algoritam filtrira proste brojeve koristeći iterativni pristup. Proces filtriranja započinje s najmanjim prostim brojem. Prost broj je prirodni broj veći od 1 koji ima samo dva djelitelja, i to 1 i sam broj. Numbers Brojevi koji nisu prosti nazivaju se složeni brojevi.

Zašto koristiti Eratostenovo sito?

U metodi Eratostenovog sita, prvo se odabire mali prosti broj, a zatim se filtriraju svi njegovi višekratnici. Proces se izvodi u petlji kroz zadani raspon, učinkovito proizvodeći svaki prosti broj do n bez izvođenja probnog dijeljenja na svakom kandidatu.

Zbog toga je sito brže od provjere primarnosti jednog broja odjednom. Široko se koristi u teoriji brojeva, kriptografiji, hashiranju i kompetitivnom programiranju gdje se mnogo prostih brojeva mora brzo generirati.

Na primjer:

Uzmimo raspon brojeva od 2 do 10.

Nakon primjene Eratostenovog sita, dobit će se 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 jednak 2), prođite kroz popis i filtrirajte odgovarajuće složene brojeve označavanjem svih višekratnika odabranog broja.

Korak 3) Zatim odaberite sljedeći prosti ili najmanji neoznačeni broj na popisu i ponovite korak 2.

Korak 4) Ponovite prethodni korak dok vrijednost x ne bude manja ili jednaka kvadratnom korijenu iz n (x <=).

Bilješka: Matematičko razmišljanje je prilično 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 <= Stoga, prolazeći do bit će dovoljno.

Korak 5) Nakon ta četiri koraka, preostali neoznačeni brojevi bit će svi prosti brojevi u zadanom rasponu n.

Obrađeni primjer

Primjer:

Uzmimo primjer i vidimo kako to 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 budući da smo odabrali n = 25.

Korak 2) Zatim odabiremo najmanji broj na popisu, x. U početku je x = 2 jer je to najmanji prosti broj. Zatim prolazimo kroz popis i označavamo višekratnike broja 2.

Višekratnici broja 2 za zadanu 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) Korak 3 ponavljamo na isti način dok ne dobijemo x = ili 5.

Korak 5) Preostali neoznačeni brojevi su prosti brojevi od 2 do 25.

Pseudo-Code

Sljedeći pseudokod obuhvaća osnovnu strukturu Eratostenovog sita prije nego što ga prevedemo u stvarni 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++ Code Primjer

Ispod je potpuni C++ implementacija Eratostenovog sita koje ispisuje svaki prosti broj do odabrane gornje granice.

#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

Sljedeće Python Program implementira isti algoritam koristeći booleovu listu i while petlju.

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 Eratostenovo sito prolazi kroz cijeli raspon brojeva. Stoga mu je potrebno O(n) memorijskog prostora za pohranu brojeva. Situacija postaje komplicirana kada pokušavamo pronaći proste brojeve u ogromnom rasponu, jer nije izvedivo dodijeliti tako veliki memorijski blok 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:

1. Pomoću jednostavnog sita pronađite proste brojeve od 2 do i pohraniti ih u niz.
2. Podijelite raspon [0…n-1] u više segmenata najviše veličine .
3. Za svaki segment, iterirajte kroz segment i označite višekratnike prostih brojeva pronađenih u koraku 1. Ovaj korak zahtijeva O() maksimalno.

Redovno sito zahtijeva O(n) pomoćnog memorijskog prostora, dok segmentirano sito zahtijeva O(), što je značajno poboljšanje za veliko n. Metoda ima i nedostatak, jer ne poboljšava vremensku složenost.

Analiza složenosti

Razumijevanje prostorne i vremenske složenosti pomaže vam u odabiru između običnog sita i segmentiranog sita za danu veličinu problema.

Složenost prostora:

Jednostavni algoritam Eratostenovog sita zahtijeva O(n) memorijskog prostora. Segmentirano sito zahtijeva O() pomoćni prostor.

Složenost vremena:

Vremenska složenost regularnog algoritma Eratostenova sita je O(n*log(log(n))). Razlog ove složenosti objašnjen je u nastavku.

Za zadani broj n, vrijeme potrebno za označavanje složenog broja (tj. broja koji nije prost) je konstantno. Dakle, broj ponavljanja 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 izvesti 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 je O(n * log(log(n))).

Zatim ćete saznati više o Pascalov trokut.

Pitanja i odgovori