Pagina Principală
Ora 13

Numere Prime

Învață să testezi dacă un număr este prim și să generezi numere prime

40min teorie + 15min probleme PbInfo
Competența 3.3
Sigla liceului
TEORIE - 40 minute

Ce vei învăța astăzi?

După această lecție, vei stăpâni testarea primalității și generarea numerelor prime folosind algoritmi eficienți.

Ce este un număr prim
Algoritmul de testare primalitate
Ciurul lui Eratostene
Generarea numerelor prime

Gândirea de bază: De ce numerele prime sunt speciale?

Analogie: Numerele prime sunt ca atomii matematicii

La fel cum atomii sunt blocurile de construcție fundamentale ale materiei, numerele prime sunt blocurile de construcție fundamentale ale numerelor!

1

Orice număr compus poate fi descompus în factori primi:

28 = 2 × 2 × 7
45 = 3 × 3 × 5
100 = 2 × 2 × 5 × 5

2

Numerele prime sunt cele care NU pot fi descompuse mai departe:

2
3
5
7
11
13

Nu există numere mai mici (în afară de 1 și ele însele) care să le împartă exact!

3

De ce e important să știm dacă un număr e prim?

  • Criptografie: Numerele prime mari protejează datele tale online
  • Matematică: Fundamentează multe teoreme importante
  • Informatică: Algoritmi eficienți pentru prelucrarea numerelor

Ce sunt Numerele Prime?

Definiție: Un număr natural p > 1 este prim dacă are exact doi divizori: 1 și pe el însuși.

Exemple: 2, 3, 5, 7, 11, 13, 17, 19, 23...

2
3
4
5
6
7
8
9
10
11
12
13

● Prim | ● Compus | ● Nici prim, nici compus (0, 1)

Verifică-ți înțelegerea:

Întrebare: De ce 1 nu este considerat număr prim?

Răspuns: Pentru că definiția spune că un număr prim trebuie să aibă exact doi divizori. 1 are doar un divizor (pe el însuși). Dacă 1 ar fi prim, descompunerea în factori primi nu ar mai fi unică!

Analogie: Cămile și încuiere

Gândește-te la numere prime ca la cămile care se încuie doar cu două chei speciale:

CAMILA 7

Doar cheia 1 și cheia 7 deschid

NUMĂR PRIM
CAMILA 12

Cheile 1,2,3,4,6,12 deschid

NUMĂR COMPUS
CAMILA 1

Doar cheia 1 deschide

NU E PRIM
REGULĂ

>1 și exact 2 divizori

DEFINIȚIE MATEMATICĂ

Algoritmul pentru Testarea Primalității

De ce ne oprim la √n? O ilustrație mentală

Imagină-ți că cauți perechi de divizori care înmulțiți dau n:

Pentru n = 36:

1 × 36 = 36
2 × 18 = 36
3 × 12 = 36
4 × 9 = 36
6 × 6 = 36 ← AICI ESTE √n!
9 × 4 = 36 (deja găsită)
12 × 3 = 36 (deja găsită)
18 × 2 = 36 (deja găsită)
36 × 1 = 36 (deja găsită)

Observație cheie: După ce trecem de √n, începem să regăsim aceleași perechi, doar inversate! Deci nu mai are rost să căutăm mai departe.

ALGORITM TestPrimSimplu VARIABILE n, d, numarDivizori: întreg ÎNCEPUT CITESTE n DACA n <= 1 ATUNCI SCRIE "NU este prim" SFÂRȘIT SFÂRȘIT DACA numarDivizori ← 0 // Parcurgem toate numerele de la 1 la n ┌ PENTRU d ← 1, n EXECUTĂ │ ┌ DACA n % d = 0 ATUNCI │ │ numarDivizori ← numarDivizori + 1 │ └ SFÂRȘIT DACA └■ ┌ DACA numarDivizori = 2 ATUNCI │ SCRIE "Este prim" │ ALTEL │ SCRIE "NU este prim" └ SFÂRȘIT DACA SFÂRȘIT

Simplu dar foarte ineficient: Pentru n=10⁶, face 1 milion de iterații. Folosit doar pentru înțelegere.

ALGORITM TestPrimOptim VARIABILE n, d: întreg prim: logic ÎNCEPUT CITESTE n // Cazuri speciale ┌ DACA n <= 1 ATUNCI │ SCRIE "NU este prim" │ SFÂRȘIT └ SFÂRȘIT DACA ┌ DACA n = 2 ATUNCI │ SCRIE "Este prim" │ SFÂRȘIT └ SFÂRȘIT DACA ┌ DACA n % 2 = 0 ATUNCI │ SCRIE "NU este prim" // Singurul număr prim par este 2 │ SFÂRȘIT └ SFÂRȘIT DACA prim ← ADEVĂRAT // Parcurgem doar divizorii impari până la √n ┌ PENTRU d ← 3, √n, 2 EXECUTĂ │ ┌ DACA n % d = 0 ATUNCI │ │ prim ← FALS │ │ OPREȘTE │ └ SFÂRȘIT DACA └■ ┌ DACA prim = ADEVĂRAT ATUNCI │ SCRIE "Este prim" │ ALTEL │ SCRIE "NU este prim" └ SFÂRȘIT DACA SFÂRȘIT

Optimizări importante:

  1. Ne oprim la √n
  2. Testăm doar divizori impari (după ce verificăm divizibilitatea cu 2)
  3. Ieșim imediat când găsim un divizor
ALGORITM CiurEratostene VARIABILE n, i, j: întreg prim: vector[1000001] de logic ÎNCEPUT CITESTE n // Inițializare: toate numerele sunt prime ┌ PENTRU i ← 2, n EXECUTĂ │ prim[i] ← ADEVĂRAT └■ // Ciurul lui Eratostene ┌ PENTRU i ← 2, √n EXECUTĂ │ ┌ DACA prim[i] = ADEVĂRAT ATUNCI │ │ // Marcăm multiplii lui i │ │ ┌ PENTRU j ← i*i, n, i EXECUTĂ │ │ │ prim[j] ← FALS │ │ └■ │ └ SFÂRȘIT DACA └■ // Afișăm numerele prime SCRIE "Numere prime până la ", n, ": " ┌ PENTRU i ← 2, n EXECUTĂ │ ┌ DACA prim[i] = ADEVĂRAT ATUNCI │ │ SCRIE i, " " │ └ SFÂRȘIT DACA └■ SFÂRȘIT
2
Prim
3
Prim
4
Multiplu de 2
5
Prim
6
Multiplu de 2,3

Cum funcționează: Începem cu 2 (prim), eliminăm toți multiplii lui 2. Trecem la 3 (prim), eliminăm multiplii lui 3, etc.

Algoritm Iterații pentru n=1.000.000 Complexitate Când să folosești
Simplu (până la n) 1.000.000 O(n) Doar pentru înțelegere concept
Optim (până la √n) 500 (doar impare) O(√n) Testare primalitate pentru un singur număr
Ciurul lui Eratostene ~784.000 O(n log log n) Când ai nevoie de toate numerele prime până la n

Exercițiu de completare - Testare primalitate:

Completează codul C++ pentru testarea primalității:
#include <iostream>
#include <cmath>
using namespace ______;
______ main() {
    int n;
    cin >> ______;
    ______ (n <= 1) { // 0 și 1 nu sunt prime
        cout << "NU";
        return ______;
    }
    ______ (n == 2) { // 2 este singurul număr prim par
        cout << "DA";
        return 0;
    }
    ______ (n % 2 == 0) { // Numerele pare mai mari decât 2 nu sunt prime
        cout << "NU";
        return 0;
    }
    ______ (int d = 3; d * d <= n; d += 2) { // Testăm doar divizorii impari până la √n
        ______ (n ______ d == 0) {
            cout << "NU";
            return 0;
        }
    }
    cout << ______; // Dacă nu am găsit divizori, numărul este prim
    return 0;
}
Bancă de cuvinte:
std int n if 0 for % DA

Test de înțelegere: Care sunt prime?

Test rapid:

Care dintre următoarele numere sunt prime?

17
21
29
33
37

Unde folosim numerele prime în viața reală?

Criptografie

Numerele prime mari (de 100+ cifre) protejează mesajele tale, tranzacțiile bancare și datele personale online.

Generare numere aleatoare

Numerele prime sunt folosite pentru a genera numere "aleatoare" de calitate în jocuri și simulări.

Algoritmi eficienți

Învățând algoritmi pentru numere prime, înveți tehnici de optimizare aplicabile în multe domenii.

Capcane comune și soluții pentru numere prime

Greșeli frecvente la testarea primalității:

❌ Uitarea cazurilor 0 și 1
// GREȘIT! 0 și 1 nu sunt prime if (n % 2 == 0) { return false; }

Soluție: Verifică întotdeauna if (n <= 1) return false;

❌ Tratarea greșită a lui 2

2 este singurul număr prim par! Algoritmul care elimină toate numerele pare ar marca și pe 2 ca neprim.

if (n == 2) return true; // Caz special if (n % 2 == 0) return false;
❌ Parcurgerea până la n în loc de √n

n=10⁹ → 1 miliard de iterații vs 31622 iterații cu metoda optimă.

Sfat pentru memorare: Regula "2-√n-2"

Pentru a testa dacă n este prim, verifică:

  1. Dacă n ≤ 1 → NU
  2. Dacă n = 2 → DA
  3. Dacă n este par → NU
  4. Verifică divizori impari până la √n

Și ieși imediat când găsești un divizor!

Best Practices pentru numere prime:

✅ Verifică întotdeauna n ≤ 1 (nu sunt prime)
✅ Tratează 2 ca caz special (singurul prim par)
✅ Testează doar până la √n pentru optimizare
✅ Testează doar divizori impari (după verificarea lui 2)
✅ Ieși imediat când găsești un divizor (break/return)
✅ Pentru multe teste, folosește Ciurul lui Eratostene
PROBLEME PBINFO - 15 minute

PbInfo #9 - Test de primalitate

Enunț:

Cerință: Se citește un număr natural n. Să se verifice dacă n este număr prim.

Date de intrare:

Programul citește de la tastatură numărul n.

Date de ieșire:

Programul va afișa pe ecran "DA" dacă n este prim, respectiv "NU" în caz contrar.

Exemplu:

Intrare:

17

Ieșire:

DA

Explicație: 17 este număr prim (are exact doi divizori: 1 și 17)

Cum gândim soluția:
  1. Citim numărul n
  2. Dacă n ≤ 1 → afișăm "NU"
  3. Dacă n == 2 → afișăm "DA" (caz special)
  4. Dacă n % 2 == 0 → afișăm "NU" (numere pare >2 nu sunt prime)
  5. Folosim for (d = 3; d * d <= n; d += 2):
    • Dacă n % d == 0 → afișăm "NU" și ieșim
  6. Dacă nu am găsit divizori → afișăm "DA"
Execuție pentru n=29:
n=29 > 1 ✓
n≠2 ✓
29%2=1 ✓ (impar)
d=3: 29%3=2 ≠0
d=5: 29%5=4 ≠0
Verificare stop: 5*5=25 ≤29 ✓ continuă
d=7: 7*7=49 >29 ✗ STOP
REZULTAT: Nu s-au găsit divizori → DA (prim)
Ce trebuie să verifici mereu?
  • Cazul n=0 și n=1: NU sunt prime
  • Cazul n=2: DA, este prim (singurul par)
  • Numere pare mai mari decât 2: NU sunt prime
  • Condiția d*d <= n pentru optimizare
  • Parcurgerea doar a divizorilor impari
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // Cazurile 0 și 1 nu sunt prime
    if (n <= 1) {
        cout << "NU";
        return 0;
    }
    
    // 2 este singurul număr prim par
    if (n == 2) {
        cout << "DA";
        return 0;
    }
    
    // Numerele pare mai mari decât 2 nu sunt prime
    if (n % 2 == 0) {
        cout << "NU";
        return 0;
    }
    
    // Verificăm divizorii impari până la √n
    for (int d = 3; d * d <= n; d += 2) {
        if (n % d == 0) {
            cout << "NU";
            return 0;
        }
    }
    
    // Dacă nu am găsit divizori, numărul este prim
    cout << "DA";
    
    return 0;
}
Varianta cu funcție:
#include <iostream>
#include <cmath>
using namespace std;

bool estePrim(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    
    for (int d = 3; d * d <= n; d += 2) {
        if (n % d == 0) {
            return false;
        }
    }
    
    return true;
}

int main() {
    int n;
    cin >> n;
    
    if (estePrim(n)) {
        cout << "DA";
    } else {
        cout << "NU";
    }
    
    return 0;
}

Ce învățăm din această problemă:

  • Optimizare matematică: Ne oprim la √n și testăm doar divizori impari
  • Cazuri speciale: 0, 1, 2 și numerele pare
  • Ieșire anticipată: Return/break imediat când găsim un divizor
  • Eficiență: Pentru n=10⁹, algoritmul face doar ~31622 iterații
  • Funcții: Organizarea codului în funcții pentru claritate

PbInfo Alternativ - Numere prime într-un interval

O problemă simplă care folosește testarea primalității într-un interval

Enunț:

Cerință: Se citesc două numere naturale a și b (a ≤ b). Să se afișeze toate numerele prime din intervalul [a, b].

Date de intrare:

Programul citește de la tastatură numerele a și b, separate prin spațiu.

Date de ieșire:

Programul va afișa pe ecran, în ordine crescătoare, toate numerele prime din intervalul [a, b], separate prin spațiu. Dacă nu există numere prime în interval, se afișează mesajul "NU EXISTA".

Exemplu:

Intrare:

10 30

Ieșire:

11 13 17 19 23 29

Explicație: Acestea sunt toate numerele prime din intervalul [10, 30].

Cum gândim soluția? Un ghid pas-cu-pas:
1

Ideea cheie: Pentru fiecare număr x de la a la b, verificăm dacă este prim.

Folosim algoritmul optimizat pe care l-am învățat (testare până la √x).

2

Cum testăm primalitatea:

  • Pentru fiecare x din interval
  • Verificăm cazurile speciale: x ≤ 1, x == 2, x % 2 == 0
  • Testăm divizori impari până la √x
  • Dacă nu găsim divizori → x este prim
3

Cum ținem evidența:

Folosim o variabilă gasit pentru a ști dacă am găsit cel puțin un număr prim.

Dacă gasit rămâne false la final, afișăm "NU EXISTA".

4

Exemplu pentru [10, 30]:

Verificăm: 10❌, 11✅, 12❌, 13✅, 14❌, 15❌, 16❌, 17✅, 18❌, 19✅, 20❌, 21❌, 22❌, 23✅, 24❌, 25❌, 26❌, 27❌, 28❌, 29✅, 30❌

Rezultat: 11 13 17 19 23 29

Cum implementăm?
  1. Citim a și b.
  2. Declarăm o variabilă gasit = false.
  3. Pentru x = a până la b:
    • Verificăm dacă x este prim (folosind algoritmul din prima problemă)
    • Dacă este prim: îl afișăm și setăm gasit = true
  4. Dacă gasit == false, afișăm "NU EXISTA".
Sfat pentru elevi:

Pentru a verifica dacă un număr este prim, copiați algoritmul din prima problemă și adaptați-l pentru fiecare x. Nu este nevoie de funcții separate - puteți scrie codul direct în loop!

Scrie soluția în C++:
Soluție corectă:
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    
    bool gasit = false; // Verificăm dacă am găsit cel puțin un număr prim
    
    // Parcurgem fiecare număr din interval
    for (int x = a; x <= b; x++) {
        // Verificăm dacă x este prim
        
        // Cazurile speciale
        if (x <= 1) {
            continue; // Trecem la următorul număr
        }
        
        if (x == 2) {
            cout << x << " ";
            gasit = true;
            continue;
        }
        
        if (x % 2 == 0) {
            continue; // Numerele pare mai mari decât 2 nu sunt prime
        }
        
        // Verificăm divizori impari până la √x
        bool estePrim = true;
        for (int d = 3; d * d <= x; d += 2) {
            if (x % d == 0) {
                estePrim = false;
                break; // Am găsit un divizor, nu mai verificăm
            }
        }
        
        // Dacă x este prim, îl afișăm
        if (estePrim) {
            cout << x << " ";
            gasit = true;
        }
    }
    
    // Dacă nu am găsit niciun număr prim
    if (!gasit) {
        cout << "NU EXISTA";
    }
    
    return 0;
}
Varianta mai compactă:
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    
    bool gasit = false;
    
    for (int x = a; x <= b; x++) {
        // Test de primalitate direct în main()
        if (x <= 1) continue;
        if (x == 2) {
            cout << x << " ";
            gasit = true;
            continue;
        }
        if (x % 2 == 0) continue;
        
        bool prim = true;
        for (int d = 3; d * d <= x; d += 2) {
            if (x % d == 0) {
                prim = false;
                break;
            }
        }
        
        if (prim) {
            cout << x << " ";
            gasit = true;
        }
    }
    
    if (!gasit) {
        cout << "NU EXISTA";
    }
    
    return 0;
}

Ce învățăm din această problemă:

  • Reutilizarea algoritmului: Folosim același algoritm de testare primalitate pentru mai multe numere
  • Structuri repetitive imbricate: Un for în interiorul altui for
  • Variabile de control: Folosim gasit pentru a ști dacă am găsit ceva
  • Optimizare: Folosim continue pentru a sări peste numerele care sigur nu sunt prime
  • Toate codul în main(): Fără funcții separate, perfect pentru începători
Verifică înțelegerea:

Întrebare: De ce folosim variabila gasit?

Răspuns: Pentru a ști dacă am găsit cel puțin un număr prim în interval. Dacă la final gasit este false, înseamnă că nu am găsit niciun număr prim și afișăm "NU EXISTA".

Execuție pentru a=10, b=15:
x=10: par → nu e prim
x=11: impar → test divizori: 3, 5, 7, 9 → gata la √11≈3.3 → PRIM ✓
x=12: par → nu e prim
x=13: impar → test: 3 → 13%3≠0 → PRIM ✓
REZULTAT: 11 13 (gasit=true)

Exercițiu Final - Contorul de numere prime

O problemă practică care testează înțelegerea completă a algoritmului

Enunț:

Cerință: Se citește un număr natural n, apoi încă n numere naturale. Să se determine câte dintre aceste n numere sunt prime.

Date de intrare:

Programul citește de la tastatură:

  1. Numărul n (câte numere urmează să fie citite)
  2. n numere naturale separate prin spațiu
Date de ieșire:

Programul va afișa pe ecran un singur număr: câte dintre cele n numere citite sunt prime.

Exemplu:

Intrare:

5
10 7 15 23 4

Ieșire:

2

Explicație: Din cele 5 numere (10, 7, 15, 23, 4), doar 7 și 23 sunt prime.

Cum gândim soluția? Un ghid pas-cu-pas:
1

Structura generală:

Citim n, apoi folosim o buclă for pentru a citi cele n numere.

2

Pentru fiecare număr citit:

  • Verificăm dacă este prim folosind algoritmul optimizat
  • Dacă este prim, creștem un contor cu 1
3

Algoritmul de verificare: Copiem codul din prima problemă PBInfo și îl adaptăm pentru fiecare număr în parte.

4

La final: Afișăm valoarea contorului.

Puncte cheie de reținut:
  • Citirea în buclă: Folosim un singur cin în interiorul buclei pentru a citi toate numerele
  • Reutilizare cod: Algoritmul de verificare primalitate este același ca în lecție
  • Contorizare: Inițializăm contor = 0 și îl incrementăm când găsim un număr prim
  • Optimizare: Nu este nevoie să memorăm toate numerele într-un vector - le procesăm pe rând
Cum eviți greșelile frecvente:

1. Nu uita să resetezi variabila care testează primalitatea pentru fiecare număr nou!
2. Folosește break când găsești un divizor, pentru a nu face verificări inutile.
3. Atenție la citire - prima valoare este n, următoarele sunt numerele de verificat.

Scrie soluția în C++:
Soluție completă și comentată:
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n; // Citim câte numere urmează
    
    int contor = 0; // Contor pentru numere prime găsite
    
    // Citim și verificăm cele n numere
    for (int i = 0; i < n; i++) {
        int x; // Variabilă pentru numărul curent
        cin >> x;
        
        // TEST DE PRIMALITATE pentru x
        // Presupunem că x este prim (true)
        bool estePrim = true;
        
        // Cazurile speciale: 0 și 1 nu sunt prime
        if (x <= 1) {
            estePrim = false;
        }
        // 2 este singurul număr prim par
        else if (x == 2) {
            // x este prim, păstrăm estePrim = true
        }
        // Numerele pare mai mari decât 2 nu sunt prime
        else if (x % 2 == 0) {
            estePrim = false;
        }
        // Verificăm divizori impari până la √x
        else {
            for (int d = 3; d * d <= x; d += 2) {
                if (x % d == 0) {
                    estePrim = false; // Am găsit un divizor
                    break; // Nu mai are rost să căutăm alți divizori
                }
            }
        }
        
        // Dacă x este prim, creștem contorul
        if (estePrim) {
            contor++;
        }
    }
    
    // Afișăm rezultatul
    cout << contor;
    
    return 0;
}
Varianta optimizată cu verificare rapidă:
#include <iostream>
using namespace std;

int main() {
    int n, contor = 0;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        
        // Verificare rapidă pentru numerele mici
        if (x <= 1) continue;       // Nu e prim
        if (x == 2) { contor++; continue; } // Este prim
        if (x % 2 == 0) continue;   // Par >2, nu e prim
        
        // Verificare divizori impari
        bool prim = true;
        for (int d = 3; d * d <= x; d += 2) {
            if (x % d == 0) {
                prim = false;
                break;
            }
        }
        
        if (prim) contor++;
    }
    
    cout << contor;
    return 0;
}

Ce învățăm din această problemă:

  • Citirea secvențială: Cum citim mai multe numere într-o buclă fără a folosi vectori
  • Procesare în flux: Prelucrăm fiecare număr imediat ce îl citim, fără a le stoca pe toate
  • Reutilizare algoritm: Aplicăm același algoritm de bază de mai multe ori
  • Contorizare: Tehnica fundamentală de numărare a elementelor care îndeplinesc o condiție
  • Optimizare memorie: Folosim doar variabile simple, nu vectori
Verifică înțelegerea:

Întrebare: De ce nu este nevoie de un vector pentru această problemă?

Răspuns: Pentru că nu trebuie să păstrăm toate numerele pentru procesări ulterioare. Le citim, verificăm dacă sunt prime și contorizăm rezultatul. Odată ce am verificat un număr, nu mai avem nevoie de el. Aceasta se numește procesare în flux.

Execuție pentru exemplul dat:
n=5 contor=0
x=10: par → nu e prim
x=7: impar → test: 3 → 7%3≠0 → PRIM ✓ contor=1
x=15: impar → test: 3 → 15%3=0 → nu e prim
x=23: impar → test: 3,5 → 23%3≠0, 23%5≠0 → PRIM ✓ contor=2
x=4: par → nu e prim
REZULTAT: contor=2
EXERCIȚII PRACTICE - 10 minute

Exercițiul Practic: Numere Prime și Proprietăți

Sarcini de lucru

Completează următoarele sarcini pentru a-ți consolida cunoștințele despre numere prime

Sarcina 1: Analiză algoritm primalitate

Analizează algoritmul optimizat pentru testarea primalității:

Pentru n=101, câte iterații face algoritmul optim vs algoritmul simplu? De ce?

Soluție pentru Sarcina 1:

Analiza pentru n=101:

  • Algoritmul simplu (până la n):
  • Parcurge toate numerele de la 1 la 101
  • Face 101 de iterații
  • Verifică pentru fiecare număr: 101%1, 101%2, ..., 101%101
  • Algoritmul optim (până la √n):
  • √101 ≈ 10.05
  • Verifică numerele: 3, 5, 7, 9
  • Face doar 4 iterații (divizori impari de la 3 la 9)
  • Optimizări aplicate:
  • 1. S-a verificat n≤1? nu (101>1)
  • 2. S-a verificat n=2? nu (101≠2)
  • 3. S-a verificat n%2==0? nu (101%2=1)
  • 4. Testează doar până la √n
  • 5. Testează doar divizori impari
  • Raport de optimizare: 101/4 ≈ 25 ori mai rapid!

Concluzie: Pentru numere mari, algoritmul optim este esențial!

Sarcina 2: Implementare în C++ pentru numere prime gemene

Cerință: Implementează în C++ un program care citește n și afișează toate perechile de numere prime gemene ≤ n (prime gemene = diferența = 2).

Soluție pentru Sarcina 2:
#include <iostream>
#include <cmath>
using namespace std;

bool estePrim(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int d = 3; d * d <= n; d += 2) {
        if (n % d == 0) return false;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    
    cout << "Perechile de numere prime gemene pana la " << n << ":" << endl;
    
    int numarPerechi = 0;
    
    // Căutăm perechi gemene (p, p+2)
    for (int p = 2; p <= n - 2; p++) {
        if (estePrim(p) && estePrim(p + 2)) {
            cout << "(" << p << ", " << p + 2 << ") ";
            numarPerechi++;
        }
    }
    
    if (numarPerechi == 0) {
        cout << "Nu exista perechi de numere prime gemene.";
    } else {
        cout << endl << "Total: " << numarPerechi << " perechi";
    }
    
    cout << endl;
    return 0;
}

Explicații importante:

  • Numere prime gemene: Perechi de numere prime cu diferența 2
  • Exemple: (3,5), (5,7), (11,13), (17,19)
  • Teste recomandate:
  • n=20 → perechi: (3,5), (5,7), (11,13), (17,19)
  • n=10 → perechi: (3,5), (5,7)
  • n=5 → perechi: (3,5)
  • n=2 → niciun număr prim gemene

Descarcă toate exercițiile și soluțiile