Numere Prime în C++ - Verificare și Utilizare

Definiție

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

Exemple:

• •Numere prime: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
• •Numere care NU sunt prime: 1 (un singur divizor), 4 (are divizorii 1, 2, 4), 6 (are divizorii 1, 2, 3, 6)

Observații importante:

• •2 este singurul număr prim par
• •1 NU este număr prim (are un singur divizor)

Teorie

Metoda 1: Verificare prin încercare de divizori (până la n-1)

Verificăm dacă există vreun divizor între 2 și n-1.

Complexitate: O(n) - ineficient pentru numere mari

Metoda 2: Verificare optimizată (până la √n)

Dacă n are un divizor d > √n, atunci n/d < √n, deci am fi găsit deja divizorul n/d.

Complexitate: O(√n) - mult mai eficient!

Exemple C++ Compilabile

Exemplul 1: Verificare dacă un număr este prim (metodă optimizată)

Copiază
1#include <iostream>
2using namespace std;
3
4int main() {
5    int n;
6    cout << "Introduceti un numar: ";
7    cin >> n;
8    
9    // Cazuri speciale
10    if (n < 2) {
11        cout << n << " NU este prim" << endl;
12        return 0;
13    }
14    
15    // Verificăm divizorii de la 2 la sqrt(n)
16    bool este_prim = true;
17    for (int d = 2; d * d <= n; d++) {
18        if (n % d == 0) {
19            este_prim = false;
20            break;
21        }
22    }
23    
24    if (este_prim)
25        cout << n << " este PRIM" << endl;
26    else
27        cout << n << " NU este prim" << endl;
28    
29    return 0;
30}

Observație: Folosim d * d <= n în loc de d <= sqrt(n) pentru a evita lucrul cu numere reale.

Exemplul 2: Funcție pentru verificare primalitate

Copiază
1#include <iostream>
2using namespace std;
3
4int estePrim(int n) {
5    if (n < 2) return 0;
6    if (n == 2) return 1;
7    if (n % 2 == 0) return 0;  // Eliminăm numerele pare
8    
9    for (int d = 3; d * d <= n; d = d + 2) {
10        if (n % d == 0)
11            return 0;
12    }
13    return 1;
14}
15
16int main() {
17    int n;
18    cin >> n;
19    
20    if (estePrim(n))
21        cout << "PRIM";
22    else
23        cout << "NU este prim";
24    
25    return 0;
26}

Exemplul 3: Afișarea numerelor prime până la n

Copiază
1#include <iostream>
2using namespace std;
3
4int estePrim(int n) {
5    if (n < 2) return 0;
6    if (n == 2) return 1;
7    if (n % 2 == 0) return 0;
8    
9    for (int d = 3; d * d <= n; d = d + 2) {
10        if (n % d == 0)
11            return 0;
12    }
13    return 1;
14}
15
16int main() {
17    int n;
18    cout << "Introduceti limita: ";
19    cin >> n;
20    
21    cout << "Numerele prime pana la " << n << " sunt: ";
22    for (int i = 2; i <= n; i++) {
23        if (estePrim(i))
24            cout << i << " ";
25    }
26    
27    return 0;
28}

Exemplul 4: Descompunerea în factori primi

Copiază
1#include <iostream>
2using namespace std;
3
4int main() {
5    int n;
6    cout << "Introduceti un numar: ";
7    cin >> n;
8    
9    cout << n << " = ";
10    int d = 2;
11    int primul = 1;  // Pentru formatare
12    
13    while (n > 1) {
14        int putere = 0;
15        while (n % d == 0) {
16            putere++;
17            n = n / d;
18        }
19        
20        if (putere > 0) {
21            if (!primul) cout << " * ";
22            cout << d;
23            if (putere > 1) cout << "^" << putere;
24            primul = 0;
25        }
26        d++;
27    }
28    
29    return 0;
30}

Exemplu de execuție:

• •Input: 360
• •Output: 360 = 2^3 * 3^2 * 5

Exemplul 5: Suma divizorilor primi

Copiază
1#include <iostream>
2using namespace std;
3
4int estePrim(int n) {
5    if (n < 2) return 0;
6    for (int d = 2; d * d <= n; d++) {
7        if (n % d == 0) return 0;
8    }
9    return 1;
10}
11
12int main() {
13    int n, suma = 0;
14    cin >> n;
15    
16    for (int d = 2; d <= n; d++) {
17        if (n % d == 0 && estePrim(d)) {
18            suma = suma + d;
19        }
20    }
21    
22    cout << "Suma divizorilor primi: " << suma << endl;
23    return 0;
24}

Greșeli Frecvente

1. Considerarea lui 1 ca număr prim

Copiază
1// GREȘIT
2if (n >= 1) return true;  // 1 NU este prim!
3
4// CORECT
5if (n < 2) return false;

2. Verificarea până la n în loc de √n

Copiază
1// INEFICIENT - O(n)
2for (int d = 2; d < n; d++) { ... }
3
4// EFICIENT - O(√n)
5for (int d = 2; d * d <= n; d++) { ... }

3. Uitarea cazului n = 2

Copiază
1// GREȘIT - 2 nu ar trece testul d * d <= n
2for (int d = 2; d * d <= n; d++) { ... }
3// Pentru n=2: 2*2 > 2, nu intră în for
4
5// CORECT - tratăm separat sau inițializăm correct
6if (n == 2) return true;

Exerciții Tip PBInfo

Exercițiul 1 - Al n-lea număr prim

Să se afișeze al n-lea număr prim.

• •Exemplu: n = 5 → Rezultat: 11 (2, 3, 5, 7, 11)

Exercițiul 2 - Numere prime gemene

Să se afișeze toate perechile de numere prime gemene (diferența = 2) până la n.

• •Exemplu: n = 20 → (3,5), (5,7), (11,13), (17,19)

Exercițiul 3 - CMMDC folosind factori primi

Să se calculeze CMMDC(a, b) folosind descompunerea în factori primi.

Exercițiul 4 - Cel mai mare factor prim

Să se afișeze cel mai mare factor prim al unui număr n.

• •Exemplu: n = 100 → Rezultat: 5

Exercițiul 5 - Ipoteza lui Goldbach

Să se verifice ipoteza lui Goldbach: orice număr par > 2 se scrie ca sumă de 2 numere prime.

• •Exemplu: n = 10 → 10 = 3 + 7 sau 10 = 5 + 5