Lectia 3: Numere prime | Clasa a X-a Mat-Info

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):

Cream o lista de n+1 valori True (presupunem ca toate sunt prime)
Marcam 0 si 1 ca False
Pornim cu p=2: marcam toti multiplii lui 2 (4,6,8,...) ca False
Urmatorul nemarat dupa 2 este 3: marcam 9, 15, 21, 27, ...
Urmatorul nemarat este 5: marcam 25, ...
p=6 → deja marcat; p=7: 7×7=49 > 30 → ne oprim
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 10⁹. Pentru verificarea unui singur numar, schimba int cu long long si conditia ramane d * d <= n. Ciurul se foloseste doar pentru n ≤ 10⁷–10⁸ (limitat de memorie RAM).

Numere prime: verificare eficienta si Ciurul lui Eratostene

Obiectivul lectiei

Dupa aceasta lectie vei putea:

Incearca singur!

1. Ce este un numar prim? Cazuri limita

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

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

4. Ciurul lui Eratostene: idee si implementare Python

5. Aplicatii practice in Python

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

Exercitii practice

Exercitiul 1 (Nivel minim) — Urmarire executie

Exercitiul 2 (Nivel standard) — Numere prime gemene

Exercitiul 3 (Nivel performanta) — Ciur cu interogari multiple

Ce ai invatat astazi

Urmatoarea lectie