Ciurul lui Eratostene - Numere Prime în C++

Ce sunt Numerele Prime?

Un număr prim este un număr natural mai mare decât 1 care are exact doi divizori: 1 și el însuși.

Algoritmul Ciurului lui Eratostene

Ideea: Marcăm succesiv multiplii fiecărui număr prim ca fiind compuși.

Implementare

Copiază
1#include <iostream>
2#include <vector>
3using namespace std;
4
5vector<int> ciurEratostene(int n) {
6    vector<bool> este_prim(n + 1, true);
7    vector<int> prime;
8    
9    este_prim[0] = este_prim[1] = false;
10    
11    for (int i = 2; i * i <= n; i++) {
12        if (este_prim[i]) {
13            // Marcăm multiplii lui i ca fiind compuși
14            for (int j = i * i; j <= n; j += i) {
15                este_prim[j] = false;
16            }
17        }
18    }
19    
20    for (int i = 2; i <= n; i++) {
21        if (este_prim[i]) {
22            prime.push_back(i);
23        }
24    }
25    
26    return prime;
27}
28
29int main() {
30    int n;
31    cout << "Introduceti limita: ";
32    cin >> n;
33    
34    vector<int> prime = ciurEratostene(n);
35    
36    cout << "Numerele prime pana la " << n << " sunt:" << endl;
37    for (int p : prime) {
38        cout << p << " ";
39    }
40    cout << endl;
41    
42    return 0;
43}

Verificare Primalitate (pentru un singur număr)

Copiază
1bool estePrim(int n) {
2    if (n < 2) return false;
3    if (n == 2) return true;
4    if (n % 2 == 0) return false;
5    
6    for (int i = 3; i * i <= n; i += 2) {
7        if (n % i == 0) return false;
8    }
9    return true;
10}

Complexitate

• •Timp: O(n * log(log(n)))
• •Spațiu: O(n)

Optimizări

1. •Ignorăm numerele pare (doar 2 este prim și par)
2. •Începem marcarea de la i*i (multiplii mai mici sunt deja marcați)