Algoritmul Sie of Eratosthenes: Python, C++ Exemplu

prin: Sarah Chen Sarah Chen
Hours Actualizat

Sita lui Eratosthenes este cea mai simplă sită a numerelor prime. Este un algoritm de numere prime pentru a căuta toate numerele prime dintr-o limită dată. Există mai multe site de numere prime. De exemplu, sita lui Eratosthenes, sita lui Atkin, sita lui Sundaram etc.

Cuvantul "sită” înseamnă o ustensilă care filtrează substanțele. Astfel, algoritmul de sită în Python și alte limbi se referă la un algoritm pentru a filtra numerele prime.

Acest algoritm filtrează numărul prim într-o abordare iterativă. Procesul de filtrare începe cu cel mai mic număr prim. Un prim este un număr natural care este mai mare decât 1 și are doar doi divizori, adică 1 și numărul însuși. Numerele care nu sunt prime se numesc numere compuse.

În sita metodei Eratosthenes, este selectat mai întâi un număr prim mic și toți multiplii acestuia sunt filtrati. Procesul rulează pe o buclă într-un interval dat.

De exemplu:

Să luăm intervalul de numere de la 2 la 10.

Algoritmul Sita lui Eratosthenes

După aplicarea Sitului lui Eratosthenes, va produce lista numerelor prime 2, 3, 5, 7

Algoritmul Sita lui Eratosthenes

Algoritmul Sita lui Eratosthenes

Iată algoritmul pentru Sita lui Eratosthenes:

Pas 1) Creați o listă de numere de la 2 la intervalul dat n. Începem cu 2, deoarece este cel mai mic și primul număr prim.

Pas 2) Selectați cel mai mic număr din listă, x (inițial x este egal cu 2), parcurgeți lista și filtrați numerele compuse corespunzătoare prin marcarea tuturor multiplilor numerelor selectate.

Pas 3) Apoi alegeți următorul număr prim sau cel mai mic număr nemarcat din listă și repetați pasul 2.

Pas 4) Repetați pasul anterior până când valoarea lui x ar trebui să fie mai mică sau egală cu rădăcina pătrată a lui n (x<=Algoritmul Sita lui Eratosthenes).

Notă: Raționamentul matematic este destul de simplu. Intervalul de numere n poate fi factorizat ca:

n=a*b

Din nou, n =Algoritmul Sita lui Eratosthenes*Algoritmul Sita lui Eratosthenes

= (factor mai mic decât Algoritmul Sita lui Eratosthenes) * (factor mai mare decât Algoritmul Sita lui Eratosthenes)

Deci cel puțin unul dintre factori primi sau ambele trebuie să fie <=Algoritmul Sita lui Eratosthenes. Astfel, traversând spre Algoritmul Sita lui Eratosthenes va fi suficient.

Pas 5) După cei patru pași, numerele rămase nemarcate ar fi toate numerele prime din intervalul dat n.

Exemplu:

Să luăm un exemplu și să vedem cum funcționează.

Pentru acest exemplu, vom găsi lista numerelor prime de la 2 la 25. Deci, n=25.

Pas 1) În primul pas, vom lua o listă de numere de la 2 la 25, deoarece am selectat n=25.

Algoritmul Sita lui Eratosthenes

Pas 2) Apoi selectăm cel mai mic număr din listă, x. Inițial x=2 deoarece este cel mai mic număr prim. Apoi parcurgem lista și marcam multiplii lui 2.

Multiplii lui 2 pentru valoarea dată a lui n sunt: ​​4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Algoritmul Sita lui Eratosthenes

Notă: Culoarea albastră indică numărul selectat, iar culoarea roz indică multiplii eliminați

Pas 3) Apoi alegem următorul cel mai mic număr nemarcat, care este 3, și repetăm ​​ultimul pas prin marcarea multiplilor lui 3.

Algoritmul Sita lui Eratosthenes

Pas 4) Repetăm ​​pasul 3 în același mod până când x=Algoritmul Sita lui Eratosthenes sau 5.

Algoritmul Sita lui Eratosthenes

Pas 5) Numerele rămase nemarcate ar fi numerele prime de la 2 la 25.

Algoritmul Sita lui Eratosthenes

ARTICOLE SIMILARE

Pseudo cod

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

Sita lui Eratostene C/C++ Exemplu de cod

#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;
}

ieșire:

2 3 5 7 11 13 17 19 23

Sita lui Eratosthenes Python Exemplu de program

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)

ieșire:

2
3
5
7
11
13
17
19
23

Sita segmentata

Am văzut că Sita lui Eratosthenes este necesară pentru a rula o buclă prin întregul interval de numere. Astfel, are nevoie de spațiu de memorie O(n) pentru a stoca numerele. Situația devine complicată atunci când încercăm să găsim numere prime într-un interval uriaș. Nu este fezabilă alocarea unui spațiu de memorie atât de mare pentru un n mai mare.

Algoritmul poate fi optimizat prin introducerea unor funcții noi. Ideea este de a împărți intervalul de numere în segmente mai mici și de a calcula numere prime în acele segmente unul câte unul. Aceasta este o modalitate eficientă de a reduce complexitatea spațiului. Această metodă se numește a sita segmentata.

Optimizarea poate fi realizată în felul următor:

  1. Folosește o sită simplă pentru a găsi numere prime de la 2 la Sita segmentata și stocați-le într-o matrice.
  2. Împărțiți intervalul [0...n-1] în mai multe segmente de dimensiune cel mult Sita segmentata
  3. Pentru fiecare segment, repetați segmentul și marcați multiplu de numere prime găsite la pasul 1. Acest pas necesită O(Sita segmentata) la max.

Sita obișnuită necesită spațiu de memorie auxiliar O(n), în timp ce sita segmentată necesită O(Sita segmentata), ceea ce este o îmbunătățire mare pentru un n mare. Metoda are un dezavantaj și pentru că nu îmbunătățește complexitatea timpului.

Analiza complexității

Complexitatea spațială:

Algoritmul sită simplă a lui Eratosthenes necesită spațiu de memorie O(n). Iar sita segmentată necesită
O(Analiza complexității) spațiu auxiliar.

Complexitatea timpului:

Complexitatea temporală a unui algoritm de sită obișnuită de eratostene este O(n*log(log(n))). Raționamentul din spatele acestei complexități este discutat mai jos.

Pentru un număr dat n, timpul necesar pentru a marca un număr compus (adică numere neprime) este constant. Deci, de câte ori se rulează bucla este egal cu-

n/2 + n/3 + n/5 + n/7 + ……∞

= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

Progresia armonică a sumei primelor poate fi dedusă ca log(log(n)).

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))

Deci, complexitatea timpului va fi-

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= n * log(log(n))

Astfel, complexitatea timpului O(n * log(log(n)))

În continuare, veți afla despre Triunghiul lui Pascal

Rezumat

  • Sita lui Eratosthenes filtrează numerele prime într-o limită superioară dată.
  • Filtrarea unui număr prim începe de la cel mai mic număr prim, „2”. Acest lucru se face iterativ.
  • Iterația se face până la rădăcina pătrată a lui n, unde n este intervalul de numere dat.
  • După aceste iterații, numerele care rămân sunt numerele prime.

S-ar putea sa-ti placa: