Invatare Atomica

Descompunere in factori primi & Divizori

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei invata sa descompui orice numar natural in factori primi, sa calculezi numarul si suma divizorilor folosind formule matematice exacte, si sa implementezi acesti algoritmi eficient in Python (si C++ la intensiv).

Dupa aceasta lectie vei putea:

  • Sa explici de ce orice numar compus se scrie unic ca produs de puteri de numere prime (Teorema Fundamentala a Aritmeticii)
  • Sa implementezi algoritmul de factorizare in O(√n) in Python
  • Sa calculezi numarul de divizori ai lui n folosind formula d(n) = (e₁+1)(e₂+1)…
  • Sa calculezi suma divizorilor cu formula sigma(n) = ∏(pe+1−1)/(p−1)
  • Sa generezi lista tuturor divizorilor in O(√n)
  • Sa rezolvi subiecte de tip BAC privind factorizarea si proprietatile divizorilor

Incearca singur!

Provocare initiala:

Descompune pe hartie numarul 72 in factori primi. Imparte succesiv la cel mai mic factor prim care divide numarul:

72 ÷ 2 = 36  |  36 ÷ 2 = 18  |  18 ÷ 2 = 9  |  9 ÷ 3 = 3  |  3 ÷ 3 = 1

Deci 72 = ? Cate numere prime apar? Cu ce exponenti?

💡 Ai nevoie de un indiciu?

Numeri de cate ori apare fiecare factor: 2 apare de 3 ori, 3 apare de 2 ori.

Deci 72 = 23 × 32. Verifica: 8 × 9 = 72. ✓

1

1. Teorema Fundamentala a Aritmeticii

Orice numar natural n > 1 se poate scrie in mod unic (pana la ordinea factorilor) ca produs de numere prime:

n = p₁e₁ × p₂e₂ × … × pkek

unde p₁ < p₂ < … < pk sunt numere prime, iar e₁, e₂, …, ek sunt exponentii lor (≥ 1).
Exemple concrete:
  • 12 = 2 × 2 × 3 = 22 × 3
  • 60 = 2 × 2 × 3 × 5 = 22 × 3 × 5
  • 72 = 2 × 2 × 2 × 3 × 3 = 23 × 32
⚠ Atentie

Cuvantul-cheie este prim: factorizarea contine DOAR numere prime. “12 = 4 × 3” NU este o factorizare in factori primi, deoarece 4 = 22 nu este prim.

2

2. Algoritmul de factorizare in Python — O(√n)

Ideea algoritmului: incercam sa impartim n la fiecare d = 2, 3, 4, … pana cand d2 > n. De fiecare data cat timp n este divizibil cu d, impartim si numaram. Daca la sfarsit n > 1, atunci n insusi este un factor prim (cel mai mare).
📈 Complexitate: O(√n)

Bucla exterioara merge pana la √n. Daca n = 106, facem cel mult 1000 de pasi. Daca n ar mai avea un factor prim p > √n, celalalt factor q = n/p < √n ar fi fost gasit deja in bucla — contradictie. Deci poate fi cel mult un astfel de factor, prins la final cu if n > 1.

# Factorizare: n = 60
def factorizare(n):
    factori = {}           # dictionar: factorul prim -> exponent
    d = 2
    while d * d <= n:      # O(sqrt(n))
        while n % d == 0:    # cat timp d divide n
            factori[d] = factori.get(d, 0) + 1
            n //= d            # elimina un factor d
        d += 1
    if n > 1:             # factorul prim mare ramas
        factori[n] = factori.get(n, 0) + 1
    return factori

n = 60
f = factorizare(n)
print("Factorizarea lui 60:")
for p, e in sorted(f.items()):
    print(f"  {p}^{e}")
termeni = [f"{p}^{e}" if e > 1 else str(p) for p, e in sorted(f.items())]
print("60 =", " * ".join(termeni))
Output real (rulat cu python):
Factorizarea lui 60:
  2^2
  3^1
  5^1
60 = 2^2 * 3 * 5
Urmarire pas cu pas pentru n = 12:

d=2: 12 % 2 == 0 → factori[2]++, n = 6

d=2: 6 % 2 == 0 → factori[2]++, n = 3

d=2: 3 % 2 != 0 → d devine 3

d=3: 3*3 = 9 > 3 → bucla while d*d ≤ n se opreste

n = 3 > 1 → factori[3]++ (factorul mare ramas)

Rezultat: 12 = 22 × 3

3

3. Numarul si suma divizorilor prin formule

Daca n = p₁e₁ × … × pkek, atunci:

Numarul de divizori: d(n) = (e₁+1)(e₂+1)…(ek+1)

Suma divizorilor: σ(n) = ∏ (pe+1−1) / (p−1)
Exemplu pentru n = 60 = 22 × 31 × 51:
  • d(60) = (2+1)(1+1)(1+1) = 3 × 2 × 2 = 12
  • σ(60) = (23−1)/(2−1) × (32−1)/(3−1) × (52−1)/(5−1) = 7 × 4 × 6 = 168
# Calcul numar si suma divizori folosind factorizarea
def factorizare(n):
    factori = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factori[d] = factori.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factori[n] = factori.get(n, 0) + 1
    return factori

def nr_divizori(factori):
    rezultat = 1
    for e in factori.values():
        rezultat *= (e + 1)   # formula (e+1)
    return rezultat

def suma_divizori(factori):
    rezultat = 1
    for p, e in factori.items():
        rezultat *= (p**(e+1) - 1) // (p - 1)  # serie geometrica
    return rezultat

n = 60
f = factorizare(n)
print(f"60 = 2^2 * 3 * 5")
print(f"Numar de divizori: {nr_divizori(f)}")
print(f"Suma divizorilor: {suma_divizori(f)}")
Output real (rulat cu python):
60 = 2^2 * 3 * 5
Numar de divizori: 12
Suma divizorilor: 168
4

4. Generarea listei divizorilor — O(√n)

Pentru a gasi toti divizorii lui n, ne folosim de simetria lor: daca i divide n, atunci si n/i divide n. Parcurgem i de la 1 la √n si colectam ambii “parteneri”. La final sortam lista.
Perechi de divizori ai lui 24:

i=1: 24/1=24 → (1, 24)  |  i=2: 24/2=12 → (2, 12)  |  i=3: 24/3=8 → (3, 8)  |  i=4: 24/4=6 → (4, 6)  |  i=5: nu divide  |  i=5: 5*5=25>24, stop.

# Lista tuturor divizorilor lui n
def divizori_lista(n):
    divs = []
    i = 1
    while i * i <= n:      # O(sqrt(n))
        if n % i == 0:
            divs.append(i)
            if i != n // i:    # evita dublarea la patrate perfecte
                divs.append(n // i)
        i += 1
    return sorted(divs)

print("Divizorii lui 24:", divizori_lista(24))
print("Numar:", len(divizori_lista(24)))
Output real (rulat cu python):
Divizorii lui 24: [1, 2, 3, 4, 6, 8, 12, 24]
Numar: 8
✅ Verificare formula

24 = 23 × 3, deci d(24) = (3+1)(1+1) = 4 × 2 = 8. Coincide cu lungimea listei de mai sus.

5

5. Aplicatii: numere speciale prin divizori

Proprietatile divizorilor stau la baza unor notiuni matematice importante frecvente la BAC si olimpiade:
  • Numar perfect: suma divizorilor proprii (fara n insusi) = n. Exemplu: 1+2+3 = 6 → 6 este perfect.
  • Numar prim: exact 2 divizori (1 si el insusi). Legatura cu factorizarea: d(p) = 2 ⇔ p prim.
  • Numar patrat perfect: are un numar impar de divizori (divizorul de la mijloc = √n).
# Verifica daca n este numar perfect
def este_perfect(n):
    s = sum(i for i in range(1, n) if n % i == 0)
    return s == n

for n in [6, 12, 28, 36]:
    print(f"{n} este perfect: {este_perfect(n)}")
Output real (rulat cu python):
6 este perfect: True
12 este perfect: False
28 este perfect: True
36 este perfect: False
6

6. Factorizare in C++ cu map EXCLUSIV INTENSIV

⚡ Sectiune doar pentru intensiv informatica

La profilul intensiv implementam factorizarea in C++ folosind map<int,int> (echivalentul dict din Python) si structured bindings din C++17 (auto& [p, e]). Acelasi algoritm O(√n), alta sintaxa.

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

map<int, int> factorizare(int n) {
    map<int, int> f;
    for (int d = 2; d * d <= n; d++) {
        while (n % d == 0) { f[d]++; n /= d; }
    }
    if (n > 1) f[n]++;
    return f;
}

int main() {
    int n = 360;
    auto f = factorizare(n);
    cout << "360 = ";
    bool first = true;
    for (auto& [p, e] : f) {   // C++17 structured bindings
        if (!first) cout << " * ";
        cout << p << "^" << e;
        first = false;
    }
    cout << endl;
    int nd = 1;
    for (auto& [p, e] : f) nd *= (e + 1);
    cout << "Numar de divizori: " << nd << endl;
    return 0;
}
Output real (compilat g++ -std=c++17, rulat):
360 = 2^3 * 3^2 * 5^1
Numar de divizori: 24
📈 Verificare independenta

360 = 23 × 32 × 51, deci d(360) = (3+1)(2+1)(1+1) = 4×3×2 = 24. Coincide cu outputul programului.

Exercitii practice

Exercitiul 1 (Nivel minim) — Factorizare manuala

Descompune in factori primi numerele 48 si 100. Verifica prin inmultire. Cati divizori are fiecare?

Indiciu: 48 = 16 × 3; 100 = 4 × 25. Descompune mai departe fiecare factor compus.

Exercitiul 2 (Nivel standard) — Program Python complet

Scrie un program Python care citeste n de la tastatura si afiseaza: factorizarea, toti divizorii (lista sortata), numarul si suma divizorilor.

Testeaza cu n = 360. Raspuns asteptat: 360 = 23 × 32 × 5, d(360) = 24, σ(360) = 1170.

Exercitiul 3 (Nivel performanta) — Subiect tip BAC avansat

Fie n un numar natural cu exact 3 divizori. Arata ca n este patratul unui numar prim. Scrie un program Python care gaseste toate astfel de numere mai mici decat 200.

Indiciu: d(n) = 3 inseamna (e₁+1) = 3 deci e₁ = 2, n = p2. Raspuns: 4, 9, 25, 49, 121, 169.

Ce ai invatat astazi

  • TFA: orice n > 1 se scrie unic ca produs de puteri de prime
  • Algoritmul de factorizare: impartiri succesive la d de la 2 la √n; complexitate O(√n)
  • Numarul de divizori: d(n) = ∏(ei+1)
  • Suma divizorilor: σ(n) = ∏(pe+1−1)/(p−1)
  • Lista divizorilor in O(√n) exploatand simetria perechilor (i, n/i)
  • C++ (intensiv): map<int,int> cu structured bindings C++17

Urmatoarea lectie

Continua cu Lectia 5: Introducere in recursivitate — vei vedea cum factorialul, CMMDC si puterea se pot calcula elegant prin apeluri recursive.

Continua →