Invatare Atomica

Numere prime: verificare eficienta si Ciurul lui Eratostene

Nota curriculara: Conform programei oficiale (OMEN 3393/2017), numerele prime si Ciurul lui Eratostene se predau la clasa a IX-a (domeniu 2.2). Aceasta lectie le recapituleaza la cls. X ca fundament necesar pentru algoritmii de clasa a X-a (factorizare, Greedy, Divide et Impera) si pentru pregatirea BAC-ului.

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei stapani doua tehnici fundamentale de lucru cu numere prime: verificarea primaltatii unui singur numar in O(√n) si generarea tuturor numerelor prime dintr-un interval cu Ciurul lui Eratostene in O(n log log n). Ambele sunt cerute la Bacalaureat si la concursuri.

Dupa aceasta lectie vei putea:

  • Sa definesti un numar prim si sa identifici cazurile limita (0, 1, 2)
  • Sa explici de ce este suficient sa verifici divizori pana la √n (nu pana la n)
  • Sa implementezi verificarea primaltatii in O(√n) in Python
  • Sa descrii si sa implementezi Ciurul lui Eratostene pas cu pas
  • Sa compari complexitatile O(n) si O(√n) si O(n log log n) si sa alegi algoritmul potrivit
  • Sa rezolvi exercitii de tip BAC cu numere prime si ciur

Incearca singur!

Provocare de gandire:

Vrei sa afli daca 97 este prim. Fara calculator, pana la ce numar ar trebui sa verifici daca se divide? Noteaza raspunsul inainte sa citesti lectia.

💡 Ai nevoie de un indiciu?

Calculeaza √97 ≈ 9.8. Deci trebuie sa verifici impartiri doar cu 2, 3, 5, 7 (primele numere pana la 9). Daca niciunul nu divide 97, el este prim!

97 / 2 = 48.5 (nu), 97 / 3 = 32.3 (nu), 97 / 5 = 19.4 (nu), 97 / 7 = 13.8 (nu) → 97 este prim.

1

1. Ce este un numar prim? Cazuri limita

Un numar natural p este prim daca are exact doi divizori naturali distincti: 1 si p.
Cazuri importante de retinut:
  • 0 → NU este prim (are o infinitate de multipli, nu are exact 2 divizori)
  • 1 → NU este prim (are un singur divizor: pe el insusi)
  • 2 → ESTE prim si este singurul numar prim par
  • 3, 5, 7, 11, 13, ... → toate prime (impare)
  • 4, 6, 8, 9, ... → compuse (au mai mult de 2 divizori)
De ce conteaza cazul 1?

Teorema fundamentala a aritmeticii spune ca orice numar natural mai mare ca 1 se scrie unic ca produs de numere prime. Daca 1 ar fi prim, aceasta unicitate s-ar pierde (am putea scrie 6 = 2 × 3 = 1 × 2 × 3 = 1 × 1 × 2 × 3 etc.). De aceea matematicienii au exclus 1 din definitia numerelor prime.

2

2. De ce verificam pana la √n? (demonstratie)

Teorema: Daca n este compus (are un factor diferit de 1 si n), atunci are un factor mai mic sau egal cu √n.
Demonstratie:

Presupunem ca n = a × b, unde 1 < a ≤ b < n.
Atunci: a × a ≤ a × b = n, deci a ≤ √n.
Concluzie: Daca n nu are niciun factor in intervalul [2, √n], atunci n este prim.

Exemplu numeric: n = 36

√36 = 6. Factorizare: 36 = 4 × 9 = 2 × 18 = 3 × 12 = 6 × 6.
Cel mai mic factor (2) este ≤ 6. ✓
Deci verificam: 36 % 2 = 0 → gasit! Nu mai continuam.

Comparatie de complexitate:
  • Varianta naiva (verificare pana la n): O(n) pasi
  • Varianta eficienta (verificare pana la √n): O(√n) pasi
  • Diferenta: pentru n = 1.000.000, naiv = 1.000.000 pasi, eficient = 1.000 pasi
3

3. Implementare Python: verificare in O(√n)

Implementam functia este_prim(n) cu optimizarile: tratam separat cazurile speciale, sarim numerele pare, si verificam doar divisori impari pana la √n.

# Verificare primalitate eficienta - O(sqrt(n))
def este_prim(n):
    if n < 2:
        return False        # 0 si 1 nu sunt prime
    if n == 2:
        return True         # 2 este singurul numar prim par
    if n % 2 == 0:
        return False        # numerele pare > 2 nu sunt prime
    d = 3
    while d * d <= n:       # echivalent: d <= sqrt(n)
        if n % d == 0:
            return False    # am gasit un factor
        d += 2              # sarim numerele pare (sunt deja excluse)
    return True

print("este_prim(1)  =", este_prim(1))
print("este_prim(2)  =", este_prim(2))
print("este_prim(7)  =", este_prim(7))
print("este_prim(9)  =", este_prim(9))
print("este_prim(97) =", este_prim(97))
print("este_prim(100)=", este_prim(100))
Output real (python C:/tmp/prime_check2.py):
este_prim(1)  = False
este_prim(2)  = True
este_prim(7)  = True
este_prim(9)  = False
este_prim(97) = True
este_prim(100)= False
Urmarire pas cu pas pentru n=9:

n=9, n≥2 ✓, n≠2 ✓, 9%2=1≠0 ✓
d=3: 3×3=9 ≤ 9 ✓, 9%3=0 → return False (9=3×3 este compus)

4

4. Ciurul lui Eratostene: idee si implementare Python

Ciurul lui Eratostene genereaza TOATE numerele prime pana la n intr-un singur pas. Complexitate: O(n log log n) — practic aproape liniar.
Algoritmul pas cu pas (pentru n=30):
  1. Cream o lista de n+1 valori True (presupunem ca toate sunt prime)
  2. Marcam 0 si 1 ca False
  3. Pornim cu p=2: marcam toti multiplii lui 2 (4,6,8,...) ca False
  4. Urmatorul nemarat dupa 2 este 3: marcam 9, 15, 21, 27, ...
  5. Urmatorul nemarat este 5: marcam 25, ...
  6. p=6 → deja marcat; p=7: 7×7=49 > 30 → ne oprim
  7. Numerele ramase True: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
# Ciurul lui Eratostene - O(n log log n)
def ciur_eratostene(n):
    # Initializam: presupunem ca toate numerele sunt prime
    prim = [True] * (n + 1)
    prim[0] = False
    prim[1] = False
    p = 2
    while p * p <= n:
        if prim[p]:
            # Marcam multiplii lui p ca non-prime
            # Incepem de la p*p (multiplii mai mici deja marcati)
            for multiplu in range(p * p, n + 1, p):
                prim[multiplu] = False
        p += 1
    # Colectam numerele ramase marcate True
    return [i for i in range(n + 1) if prim[i]]

prime = ciur_eratostene(30)
print("Numerele prime pana la 30:")
print(prime)
Output real (python C:/tmp/prime_sieve.py):
Numerele prime pana la 30:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
De ce incepem de la p*p?

Cand ajungem la p=5, multiplii 2×5=10, 3×5=15, 4×5=20 au fost deja marcati de 2, respectiv de 3 si 2. Primul multiplu al lui 5 care nu a fost marcat este 5×5=25. Aceasta optimizare reduce numarul total de operatii.

5

5. Aplicatii practice in Python

Folosim functia este_prim pentru aplicatii frecvente la BAC si concursuri.

# Primele 10 numere prime
prime10 = []
n = 2
while len(prime10) < 10:
    if este_prim(n):
        prime10.append(n)
    n += 1
print("Primele 10 numere prime:", prime10)

# Numarare prime intr-un interval
a, b = 10, 50
count = sum(1 for x in range(a, b + 1) if este_prim(x))
print(f"Numarul de prime in [{a}, {b}]: {count}")
Output real (python inline):
Primele 10 numere prime: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Numarul de prime in [10, 50]: 11
Cand sa folosesti este_prim vs ciur?
  • este_prim(n): cand testezi un singur numar sau putine numere. Cost: O(√n) per apel.
  • ciur_eratostene(n): cand ai nevoie de TOATE primele pana la n. Cost total: O(n log log n), indiferent de cate prime ai. Mult mai eficient pentru interogari multiple.
6

6. Implementare C++ — verificare si ciur EXCLUSIV INTENSIV

⚡ Sectiune doar pentru intensiv informatica

In C++ scriem aceleasi algoritme cu avantajul tipizarii explicite si al optimizarilor de memorie (vector<bool> stocheaza fiecare bit pe 1 bit, de 8x mai eficient decat vector<char>). La intensiv C++ este obligatoriu alaturi de Python.

Verificare primalitate O(√n) in C++:

#include <iostream>
using namespace std;

bool estePrim(int n) {
    if (n < 2) 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 teste[] = {1, 2, 7, 9, 97, 100};
    for (int x : teste) {
        cout << "estePrim(" << x << ") = "
             << (estePrim(x) ? "true" : "false") << endl;
    }
    return 0;
}
Output real (g++ -std=c++17 C:/tmp/prime_cpp.cpp -o C:/tmp/prime_cpp.exe && C:/tmp/prime_cpp.exe):
estePrim(1) = false
estePrim(2) = true
estePrim(7) = true
estePrim(9) = false
estePrim(97) = true
estePrim(100) = false

Ciurul lui Eratostene cu vector<bool> in C++:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 30;
    // vector<bool>: fiecare element ocupa 1 bit (eficient pentru n mare)
    vector<bool> prim(n + 1, true);
    prim[0] = false;
    prim[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (prim[p]) {
            for (int m = p * p; m <= n; m += p) {
                prim[m] = false;
            }
        }
    }
    cout << "Numerele prime pana la " << n << ": ";
    for (int i = 2; i <= n; i++) {
        if (prim[i]) cout << i << " ";
    }
    cout << endl;
    return 0;
}
Output real (g++ -std=c++17 C:/tmp/ciur_cpp.cpp -o C:/tmp/ciur_cpp.exe && C:/tmp/ciur_cpp.exe):
Numerele prime pana la 30: 2 3 5 7 11 13 17 19 23 29
Nota despre tipuri: long long pentru n mare (EXCLUSIV INTENSIV)

La concursuri, n poate fi pana la 109. Pentru verificarea unui singur numar, schimba int cu long long si conditia ramane d * d <= n. Ciurul se foloseste doar pentru n ≤ 107–108 (limitat de memorie RAM).

Exercitii practice

Exercitiul 1 (Nivel minim) — Urmarire executie

Urmareste manual executia este_prim(25) pas cu pas. Ce valoare are d cand se returneaza False? De ce nu se verifica d=7?

Vezi rezolvarea

Urmarire executie este_prim(25):

  1. n=25, n<2? Nu.
  2. n==2? Nu.
  3. n%2==0? 25%2=1, Nu (e impar).
  4. d=3. Verificam d*d<=n: 3*3=9<=25, da. 25%3=1 (25=3*8+1), nu e divizor. d+=2, d=5.
  5. Verificam d*d<=n: 5*5=25<=25, da. 25%5=0, am gasit un factor, return False.

Raspuns: functia returneaza False cand d=5, pentru ca 25=5*5 si 25%5==0.

De ce nu se verifica d=7? Pentru ca functia s-a oprit deja la d=5 (a gasit factorul si a facut return). Chiar daca n-ar fi gasit factorul la d=5, dupa d+=2 am avea d=7, iar conditia d*d<=n devine 7*7=49<=25, falsa (49>25). Bucla s-ar opri oricum, pentru ca radacina din 25 este 5.

Exercitiul 2 (Nivel standard) — Numere prime gemene

Doua numere prime care difera prin 2 se numesc prime gemene (ex: 3 si 5, 11 si 13). Scrie un program Python care afiseaza toate perechile de prime gemene mai mici decat 100. Foloseste functia este_prim deja scrisa.

Vezi rezolvarea

Idea: parcurgem n de la 2 la 97 si verificam daca este_prim(n) si este_prim(n+2) sunt ambele True.

for n in range(2, 98): if este_prim(n) and este_prim(n+2): print(n, n+2)

Perechile gasite (8 perechi):

  1. (3, 5)
  2. (5, 7)
  3. (11, 13)
  4. (17, 19)
  5. (29, 31)
  6. (41, 43)
  7. (59, 61)
  8. (71, 73)

Observatie: (89, 91) nu e pereche prima, pentru ca 91=7*13 nu e prim.

Exercitiul 3 (Nivel performanta) — Ciur cu interogari multiple

Primesti N interogari, fiecare cu un numar x (1 ≤ x ≤ 106). Pentru fiecare, afiseaza daca x este prim. Compara doua abordari: (a) apelezi este_prim(x) pentru fiecare interogare; (b) precalculezi ciurul o singura data si raspunzi la fiecare interogare in O(1). Scrie ambele variante si discuta complexitatea totala pentru N=100.000 interogari.

Vezi rezolvarea

Schita de rezolvare (nu solutia completa):

  1. Varianta (a): pentru fiecare din cele N interogari apelezi direct este_prim(x). Costul per interogare e O(radical din x), deci costul total e O(N * radical din x_max).
  2. Varianta (b): construiesti O SINGURA DATA ciur_eratostene(10**6), apoi pentru fiecare interogare citesti direct prim[x] in O(1). Costul total e O(M log log M + N), unde M=10^6.
  3. Capcana: ciurul trebuie construit o singura data, INAINTE de a citi interogarile, altfel pierzi tot avantajul.

Calcul numeric pentru N=100.000: (a) aproximativ 100.000 x 1.000 = 10^8 operatii (lent in Python); (b) aproximativ 10^6 x 3 (ciurul) + 100.000 (interogarile) = circa 3,1 milioane operatii, mult mai rapid.

Criterii de evaluare: ciurul corect implementat; alegerea motivata a variantei (b) pentru N mare; cifrele de complexitate calculate concret, nu doar "O mare".

Ce ai invatat astazi

  • Definitia numarului prim: exact 2 divizori (1 si el insusi); 0 si 1 nu sunt prime
  • De ce este suficient sa verifici pana la √n: daca n=a×b, cel mai mic factor a ≤ √n
  • Verificare primalitate eficienta: O(√n) in Python (si C++ la intensiv)
  • Ciurul lui Eratostene: genereaza toate primele pana la n in O(n log log n)
  • Optimizarea ciurului: marcarea incepe de la p*p (multiplii mai mici deja marcati)
  • Alegerea algoritmului: este_prim pentru un numar, ciur pentru interogari multiple

Vrei mai mult?

Provocare: Genereaza cu Ciurul lui Eratostene toate numerele prime pana la 100. Apoi, pentru fiecare numar par n intre 4 si 100, gaseste o pereche de numere prime p + q = n (Conjectura lui Goldbach) si afiseaz-o. Exista vreun n par pentru care nu gasesti nicio pereche?

De gandit: Ciurul marcheaza multiplii fiecarui numar prim gasit, deci la prima vedere pare sa "atinga" fiecare numar de mai multe ori. De ce complexitatea totala ramane O(n log log n) si nu O(n log n) sau O(n^2)? Ce se intampla cu numarul de multipli marcati pe masura ce p creste?

Dincolo de lectie: Ciurul lui Eratostene e rapid, dar nu scaleaza la numerele de sute de cifre folosite in criptografia RSA - acolo ar dura mai mult decat varsta universului. De aceea sistemele reale (OpenSSL, browsere) folosesc teste probabilistice precum Miller-Rabin, care decid cu probabilitate foarte mare daca un numar urias e prim, in fractiuni de secunda.

Urmatoarea lectie

Continua cu lectia urmatoare: Descompunere in factori primi — vei vedea cum primalitatea si ciurul se combina cu factorizarea pentru a rezolva probleme avansate (numar de divizori, suma divizorilor).

Continua →