Descompunerea în factori primi

De ce contează?

Orice număr e ca un mecanism construit din piese standard: numerele prime. 60 se „desface" în 2, 2, 3 și 5 — și nu există altă combinație de prime care să-l reconstruiască. Această desfacere unică e descompunerea în factori primi.

Ce este descompunerea în factori primi

Orice număr n ≥ 2 se scrie în mod unic ca produs de numere prime:

60 = 2² · 3 · 5

Asta e teorema fundamentală a aritmeticii: descompunerea există și e unică (până la ordine).

Ideea algoritmului

Pornim cu cel mai mic factor posibil (2) și „scoatem" tot ce putem, apoi trecem la următorul. Cheia: când împărțim repetat la un factor, restul nu mai conține acel factor.

factori

Factorii primi ai lui 60. Înmulțiți la loc dau exact 60 = 2·2·3·5. Niciun alt set de prime nu reconstruiește 60.

Algoritm pas cu pas: n = 60

Factor `d`	împărțim cât putem	rămâne `n`
2	60 → 30 → 15	15 (2 apare de 2 ori)
3	15 → 5	5 (3 apare o dată)
5	5 → 1	1 (5 apare o dată)

Rezultat: 2² · 3 · 5.

Implementare C++

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            int putere = 0;
            while (n % d == 0) {      // scoatem tot factorul d
                n /= d;
                putere++;
            }
            cout << d << "^" << putere << " ";
        }
    }
    if (n > 1) {                       // factorul prim mare ramas
        cout << n << "^1";
    }
    cout << "\n";
    return 0;
}

Pentru n = 60 afișează 2^2 3^1 5^1.

Observația-cheie

Linia if (n > 1) de la final e esențială. După buclă, dacă a mai rămas ceva peste 1, e un factor prim mai mare decât √n (poate exista cel mult unul). Fără această linie ai rata, de exemplu, factorul 7 din n = 14.

De ce ne oprim la √n în buclă

Un factor mai mare decât √n nu poate apărea decât o singură dată (altfel produsul ar depăși n). Deci după ce am scos toți factorii mici, ce rămâne e fie 1, fie acel unic factor prim mare. Bucla merge până la √n, iar if (n > 1) îl prinde pe ultimul.

Complexitate

Caz	Timp	Spațiu
oricare	O(√n)	O(1)

Pentru n = 10¹², √n = 10⁶ pași — rapid. Folosit des la indicatorul lui Euler și la numărarea divizorilor.

Greșeli frecvente

Capcane reale la descompunere:

Uiți if (n > 1) la final: ratezi factorul prim mare. Pentru n = 14 ai scoate doar 2 și ai pierde 7.
Nu împarți repetat: scoți factorul o singură dată și ratezi puterea (8 = 2³ ai raporta ca 2¹). Folosește bucla interioară while.
Overflow în d * d: la n mare, d * d se sparge în int. Lucrează pe long long.
Pornești de la 1: factorul 1 ar produce buclă infinită (n % 1 == 0 mereu). Pornește de la 2.

De reținut

Orice n ≥ 2 = produs unic de prime (ex. 60 = 2²·3·5).
Scoți fiecare factor cât poate (bucla while) și mergi cu d până la √n.
if (n > 1) la final prinde unicul factor prim mai mare decât √n.