Programare Competitivă

Descompunerea în factori primi

Teorema fundamentală a aritmeticii spune că orice număr natural N ≥ 2 se poate scrie în mod unic (până la ordinea factorilor) ca un produs de numere prime.

12 = 2 · 2 · 3 = 2² · 3
60 = 2² · 3 · 5
100 = 2² · 5²
2024 = 2³ · 11 · 23

Această descompunere e ca „ADN-ul” numărului — arată din ce „cărămizi prime” e construit. Multe probleme grele de teoria numerelor (CMMDC, CMMMC, numărul divizorilor, funcția Euler) se reduc la a ști factorizarea.

Algoritmul clasic — împărțiri succesive

Idee: încercăm fiecare posibil factor d = 2, 3, 4, 5, ... Cât timp N e divizibil cu d, împărțim și numărăm de câte ori.

pentru d = 2, 3, 4, ... până când d² > N:
    cât timp N % d == 0:
        scriem d ca factor
        N = N / d
dacă la final N > 1, atunci N însuși e prim

De ce funcționează?

Dacă d ajunge la un număr compus (ex. 6), divizorii lui primi (2, 3) au fost deja epuizați — N nu mai e divizibil cu ei. Deci nici cu 6 nu e. Nu trebuie să testăm dacă d e prim — vor „cădea” singuri.

De ce oprirea la d² > N?

Dacă N rămas e > 1 după ce am testat toți d cu d² ≤ N, atunci N e prim. Nu poate avea factori mai mici (i-am epuizat), iar un factor compus ≥ √N ar avea un perechi < √N.

Pas cu pas: factorizarea lui 360

N = 360
d = 2:  360 / 2 = 180 (factor 2, count=1)
        180 / 2 = 90  (count=2)
         90 / 2 = 45  (count=3)
        45 nu e divizibil cu 2.
d = 3:  45 / 3 = 15 (factor 3, count=1)
        15 / 3 = 5  (count=2)
        5 nu e divizibil cu 3.
d = 4:  5 nu e divizibil cu 4.
d² = 16 > 5 → stop.
N = 5 > 1 → factor 5 (count=1)

Rezultat: 360 = 2³ · 3² · 5 ✓.

Cod

Afișare simplă

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main() {
    long long n;
    fin >> n;

    for (long long d = 2; d * d <= n; d++) {
        while (n % d == 0) {
            fout << d << " ";
            n /= d;
        }
    }
    if (n > 1) fout << n;
    return 0;
}

Complexitate: O(√N) în cel mai rău caz (când N e prim).

Ca vector de perechi (factor, putere)

Util când vrem să manipulăm factorizarea, nu doar să o afișăm:

#include <vector>
using namespace std;

vector<pair<long long, int>> factorizeaza(long long n) {
    vector<pair<long long, int>> rez;
    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            int cnt = 0;
            while (n % d == 0) { n /= d; cnt++; }
            rez.push_back({d, cnt});
        }
    }
    if (n > 1) rez.push_back({n, 1});
    return rez;
}

Exemplu: factorizeaza(360) → [(2, 3), (3, 2), (5, 1)].

Factorizare rapidă cu ciurul (când avem multe numere de factorizat)

Dacă trebuie să factorizăm multe numere până la N, putem precalcula cu ciurul modificat: pentru fiecare număr i, memorăm cel mai mic factor prim lp[i].

Precalcul ciur cu factor minim

const int NMAX = 1e6 + 5;
int lp[NMAX]; // cel mai mic factor prim al lui i

void ciurLP(int n) {
    for (int i = 2; i <= n; i++) {
        if (lp[i] == 0) {
            // i e prim
            for (int j = i; j <= n; j += i) {
                if (lp[j] == 0) lp[j] = i;
            }
        }
    }
}

Complexitate: O(N log log N).

Factorizare în O(log N)

Odată ce avem lp[], factorizarea oricărui n ≤ N e:

vector<pair<int, int>> factorRapid(int n) {
    vector<pair<int, int>> rez;
    while (n > 1) {
        int p = lp[n], cnt = 0;
        while (n % p == 0) { n /= p; cnt++; }
        rez.push_back({p, cnt});
    }
    return rez;
}

Util la probleme unde primești Q = 10⁶ întrebări „factorizează acest număr”.

Aplicații imediate ale factorizării

1. Numărul divizorilor

Dacă N = p₁^a₁ · p₂^a₂ · ... · pₖ^aₖ, atunci numărul de divizori ai lui N e:

τ(N) = (a₁ + 1) · (a₂ + 1) · … · (aₖ + 1)

Exemplu: 360 = 2³ · 3² · 5¹ → τ(360) = 4 · 3 · 2 = 24 divizori.

long long numarDivizori(long long n) {
    long long rez = 1;
    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            int cnt = 0;
            while (n % d == 0) { n /= d; cnt++; }
            rez *= (cnt + 1);
        }
    }
    if (n > 1) rez *= 2;
    return rez;
}

2. Suma divizorilor

σ(N) = Π (p^(a+1) - 1) / (p - 1) pentru fiecare factor prim p^a

Exemplu: σ(12) = σ(2² · 3) = (2³-1)/(2-1) · (3²-1)/(3-1) = 7 · 4 = 28.
Verificare: divizorii lui 12 sunt 1, 2, 3, 4, 6, 12 → suma = 28 ✓.

3. Funcția Euler φ(N) (indicatorul lui Euler)

Numărul de întregi din 1..N coprime cu N:

φ(N) = N · Π (1 - 1/p) pentru fiecare factor prim p

Exemplu: φ(12) = 12 · (1 - 1/2) · (1 - 1/3) = 12 · 1/2 · 2/3 = 4.

long long phi(long long n) {
    long long rez = n;
    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            while (n % d == 0) n /= d;
            rez -= rez / d;
        }
    }
    if (n > 1) rez -= rez / n;
    return rez;
}

4. CMMDC și CMMMC via factorizare

Dacă a = Π p^xᵢ și b = Π p^yᵢ:

  • CMMDC(a, b) = Π p^min(xᵢ, yᵢ)
  • CMMMC(a, b) = Π p^max(xᵢ, yᵢ)

De exemplu: CMMDC(360, 84) = CMMDC(2³·3²·5, 2²·3·7) = 2² · 3 · 1 = 12.

În practică folosim algoritmul lui Euclid pentru CMMDC (mai rapid). Vezi CMMDC.

5. Număr perfect, deficient, abundent

  • Perfect: σ(N) = 2N (ex. 6 = 1+2+3, 28 = 1+2+4+7+14)
  • Deficient: σ(N) < 2N
  • Abundent: σ(N) > 2N

Numărul de divizori pentru toate 1..N

Dacă vrem τ(i) pentru toți i ≤ N, folosim un ciur „de divizori”:

int nrDiv[NMAX];

void precalcNrDiv(int n) {
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j += i)
            nrDiv[j]++;
}

Complexitate: O(N log N) (suma armonică).

Rulează pentru N = 10⁶ sub 1 secundă.

Probleme clasice

1. Cel mai mare factor prim

long long marelui(long long n) {
    long long max_p = 0;
    for (long long d = 2; d * d <= n; d++) {
        while (n % d == 0) { max_p = d; n /= d; }
    }
    if (n > 1) max_p = n;
    return max_p;
}

2. Numărul de divizori primi distincți

int nrFactoriPrimi(long long n) {
    int cnt = 0;
    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            cnt++;
            while (n % d == 0) n /= d;
        }
    }
    if (n > 1) cnt++;
    return cnt;
}

3. Verifică dacă N e o putere perfectă a unui prim

N = p^k pentru un prim p ⇔ are exact un factor prim distinct.

Tabel identități utile

Identitate Interpretare
N = p₁^a₁ · p₂^a₂ · ... · pₖ^aₖ forma canonică (unică)
τ(N) = Π (aᵢ + 1) numărul divizorilor
σ(N) = Π (p^(aᵢ+1) - 1)/(p - 1) suma divizorilor
φ(N) = N · Π (1 - 1/p) indicatorul lui Euler
CMMDC(a,b)·CMMMC(a,b) = a·b relație clasică
μ(N) = 0 dacă N are un factor pătrat funcția Möbius

Greșeli frecvente

1. Depășirea la d * d

Pentru long long mare, d * d poate depăși. Alternativ scrie d <= n / d:

for (long long d = 2; d <= n / d; d++) { ... }

2. A uita factorul „rămas” > 1

După bucla principală, dacă n > 1, ceea ce a mai rămas e un factor prim (> √N original). Nu uita să-l adaugi.

3. Testarea inutilă a numerelor pare > 2

Optimizare: testează d = 2 separat, apoi doar impare:

while (n % 2 == 0) { /* factor 2 */ n /= 2; }
for (long long d = 3; d * d <= n; d += 2) { ... }

Rulează ~2× mai rapid.

4. Confuzia între „factor” și „divizor prim”

  • Factor prim = cifră primă din descompunere.
  • Divizor = orice număr care împarte N (inclusiv 1, N, și produsele parțiale).

12 are 2 factori primi (2, 3) dar 6 divizori (1, 2, 3, 4, 6, 12).

Ce să reții

  • Orice N ≥ 2 se descompune unic ca produs de puteri de prime.
  • Algoritmul clasic: for d = 2 to √N, while N % d == 0 { scoate d }, iar ce rămâne > 1 e prim.
  • Complexitate: O(√N) per factorizare.
  • Pentru multe numere, precalculează lp[] (cel mai mic factor prim) cu ciurul → O(log N) per factorizare.
  • Aplicații: număr divizori, sumă divizori, φ Euler, CMMDC, numere perfecte.
  • Nu confunda factor prim cu divizor.
  • Optimizare: tratează 2 separat, apoi doar impare.

Probleme

pbinfo![https://www.pbinfo.ro/probleme/122/cifrebinare]pbinfo pbinfo![https://www.pbinfo.ro/probleme/427/bazaminima]pbinfo pbinfo![https://www.pbinfo.ro/probleme/428/transfb]pbinfo pbinfo![https://www.pbinfo.ro/probleme/3348/sumaputeri2]pbinfo

Cuprins Inapoi Inainte