Sita lui Eratostene în Python & C++
Sarah Chen
⚡ Rezumat inteligent
Sita lui Eratostene este un algoritm clasic al numerelor prime care filtrează numerele compuse prin marcarea iterativă a multiplilor fiecărui număr prim, lăsând doar numerele prime în limitele superioare alese pentru o căutare rapidă.
Ce este sita lui Eratostene?
Sita lui Eratostene este cea mai simplă sită pentru numere prime. Este un algoritm pentru numere prime folosit pentru a descoperi fiecare număr prim aflat într-o anumită limită. Există mai multe site prime, inclusiv Sita lui Eratostene, Sita lui Atkin și Sita lui Sundaram.
Cuvantul "sită„se referă la un instrument care filtrează substanțe. În același spirit, algoritmul sitei din Python și alte limbaje se referă la o metodă care filtrează numerele prime dintr-o listă de numere întregi.
Acest algoritm filtrează numerele prime folosind o abordare iterativă. Procesul de filtrare începe cu cel mai mic număr prim. Un număr prim este un număr natural mai mare decât 1 care are doar doi divizori, și anume 1 și numărul în sine. Numbers care nu sunt numere prime se numesc numere compuse.
De ce să folosim sita lui Eratostene?
În metoda sitei lui Eratostene, se selectează mai întâi un număr prim mic, iar toți multiplii acestuia sunt filtrați. Procesul rulează într-o buclă pe un interval dat, producând fiecare număr prim până la n eficient, fără a efectua împărțirea prin încercare pe fiecare candidat.
Acest lucru face ca sita să fie mai rapidă decât verificarea primalității număr cu număr. Este utilizată pe scară largă în teoria numerelor, criptografie, hashing și programare competitivă, unde trebuie generate rapid multe numere prime.
De exemplu:
Să luăm intervalul numeric de la 2 la 10.
După aplicarea sitei lui Eratostene, se vor obține lista numerelor prime 2, 3, 5, 7.
Algoritmul Sita lui Eratosthenes
Iată algoritmul pentru Sita lui Eratosthenes:
Pas 1) Creați o listă de numere de la 2 până 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 marcând toți multiplii numărului selectat.
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 este mai mică sau egală cu rădăcina pătrată a lui n (x<=
).
Notă: Raționamentul matematic este destul de simplu. Intervalul de numere n poate fi factorizat astfel:
n = a * b
Din nou, n = *
= (factor mai mic decât ) * (factor mai mare decât )
Deci cel puțin unul dintre factori primi sau ambele trebuie să fie <= Prin urmare, traversând până la va fi suficient.
Pas 5) După acești patru pași, numerele nemarcate rămase vor fi toate numerele prime din intervalul n dat.
Exemplu lucrat
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.
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 marcăm multiplii lui 2.
Multiplii lui 2 pentru valoarea dată a lui n sunt: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.
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.
Pas 4) Repetăm pasul 3 în același mod până când x = 
sau 5.
Pas 5) Numerele rămase nemarcate sunt numerele prime de la 2 la 25.
Pseudo-Code
Următorul pseudo-cod surprinde structura de bază a sitei lui Eratostene înainte de a o traduce în cod real.
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++ Code Exemplu
Mai jos este o versiune completă C++ implementarea sitei lui Eratostene care afișează fiecare număr prim până la o limită superioară aleasă.
#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
Următoarele Python Programul implementează același algoritm folosind o listă booleană și o buclă while.
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 Eratostene parcurge o buclă prin întregul interval de numere. Prin urmare, are nevoie de O(n) spațiu de memorie pentru a stoca numerele. Situația devine complicată atunci când încercăm să găsim numere prime într-un interval imens, deoarece nu este fezabil să alocăm un bloc de memorie atât de mare pentru un număr 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:
- Folosește o sită simplă pentru a găsi numere prime de la 2 la
și stocați-le într-o matrice. - Împărțiți intervalul [0...n-1] în mai multe segmente de dimensiune cel mult .
- Pentru fiecare segment, parcurgeți segmentul și marcați multiplii numerelor prime găsite în pasul 1. Acest pas necesită O() la maximum.
Sita obișnuită necesită spațiu de memorie auxiliar O(n), în timp ce sita segmentată necesită O(), ceea ce reprezintă o îmbunătățire substanțială pentru un n mare. Metoda are și un dezavantaj, deoarece nu îmbunătățește complexitatea temporală.
Analiza complexității
Înțelegerea complexității atât în spațiu, cât și în timp vă ajută să alegeți între sita obișnuită și sita segmentată pentru o anumită dimensiune a problemei.
Complexitatea spațială:
Algoritmul simplu al sitei lui Eratostene necesită O(n) spațiu de memorie. Sita segmentată necesită O() spațiu auxiliar.
Complexitatea timpului:
Complexitatea temporală a unui algoritm obișnuit al sitei lui 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ă un număr neprim) este constant. Deci, numărul de execuții ale buclei este egal cu:
n/2 + n/3 + n/5 + n/7 + ……∞
= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)
Progresia armonică a sumei numerelor prime poate fi dedusă ca log(log(n)):
(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))
Deci, complexitatea temporală va fi:
T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)
= n * log(log(n))
Astfel, complexitatea temporală este O(n * log(log(n))).
În continuare, veți afla despre Triunghiul lui Pascal.
