Descompunerea în factori primi

Algoritmul care scoate factorii primi și exponenții lor, de ce merge fără test de primalitate și ce faci cu restul rămas.

Ce se cere

Orice număr natural mai mare decât 1 se scrie, într-un singur fel, ca produs de puteri de numere prime:

360 = 2³ · 3² · 5
84  = 2² · 3 · 7
97  = 97          (e prim)

Problema tipică: se citește n și se cer factorii primi cu exponenții lor.

Algoritmul

int d = 2;
while (n > 1) {
    int e = 0;
    while (n % d == 0) {
        e++;
        n /= d;
    }
    if (e > 0)
        cout << d << " " << e << "\n";
    d++;
}

Pentru n = 360 afișează 2 3, 3 2, 5 1.

Sunt două bucle. Cea exterioară trece prin candidați, iar cea interioară scoate un candidat de câte ori se poate.

De ce nu trebuie să testăm dacă `d` este prim

Aceasta e partea ingenioasă a algoritmului. Încearcă s-o înțelegi, nu s-o memorezi.

Când ajungem la d = 4, toți factorii 2 au fost deja scoși din n. Deci n nu se mai divide cu 2 și, prin urmare, nici cu 4. La fel se întâmplă cu 6, 8, 9 și cu toate celelalte numere compuse: factorii lor primi au fost eliminați mai devreme.

Orice d care divide pe n în acest moment este obligatoriu prim. Nu mai e nevoie de niciun test.

Oprirea la √n

Bucla de mai sus merge până când n devine 1. Dacă n este prim și mare, d urcă până la n, adică face n pași.

Ca la divizori, ne putem opri la √n:

int d = 2;
while (d * d <= n) {
    int e = 0;
    while (n % d == 0) {
        e++;
        n /= d;
    }
    if (e > 0)
        cout << d << " " << e << "\n";
    d++;
}
if (n > 1)
    cout << n << " " << 1 << "\n";

Ultima linie e esențială și mulți o uită. Dacă după buclă a rămas ceva mai mare decât 1, acel rest este el însuși un număr prim. E un factor prim mai mare decât √n și nu poate exista decât unul, pentru că doi astfel de factori ar avea produsul mai mare decât n.

Pentru n = 2 · 3 · 101 = 606, bucla scoate 2 și 3 și ajunge la n = 101. Bucla mai încearcă d = 4, 5, …, 10 și se oprește la d = 11, pentru că 11·11 = 121 > 101. Ultima linie afișează 101 1.

Ce se calculează din descompunere

Numărul de divizori. Dacă n = p₁^e₁ · p₂^e₂ · … · pₖ^eₖ, atunci numărul de divizori este (e₁+1)(e₂+1)…(eₖ+1).

Pentru 360 = 2³·3²·5¹: (3+1)(2+1)(1+1) = 24 de divizori.

long long cati = 1;
int d = 2;
while (d * d <= n) {
    int e = 0;
    while (n % d == 0) { e++; n /= d; }
    cati *= (e + 1);
    d++;
}
if (n > 1) cati *= 2;
cout << cati;

Metoda e mult mai rapidă decât să numeri divizorii unul câte unul. Tot ea explică de ce numerele cu mulți divizori mici au foarte mulți divizori în total.

Cel mai mare factor prim. Rulezi același algoritm și reții ultimul d găsit sau restul, dacă rămâne peste 1.

Dacă un număr este putere a unui prim. Este atunci când descompunerea are un singur factor.

O capcană

Algoritmul modifică n. Dacă trebuie să-l afișezi la final sau să-l compari, ține o copie:

int copie = n;
// … descompunerea distruge n …
cout << copie << " are " << cati << " divizori";

Un exemplu complet

Se citește n. Să se afișeze descompunerea în forma 2^3*3^2*5.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    bool primul = true;
    for (int d = 2; d * d <= n; d++) {
        int e = 0;
        while (n % d == 0) { e++; n /= d; }
        if (e > 0) {
            if (!primul) cout << "*";
            cout << d;
            if (e > 1) cout << "^" << e;
            primul = false;
        }
    }
    if (n > 1) {
        if (!primul) cout << "*";
        cout << n;
    }

    return 0;
}

Indicatorul primul există ca să nu pui * înaintea primului factor. E un tipar mărunt, pe care îl folosești de fiecare dată când afișezi o listă cu separator între elemente.

De reținut

Scoate fiecare factor de câte ori se poate, apoi treci la următorul candidat.
Nu trebuie să testezi dacă d este prim, pentru că factorii compuși au dispărut deja.
Oprește-te la √n și tratează restul: dacă la final n > 1, acesta e un factor prim.
Numărul de divizori se obține înmulțind, pentru fiecare factor prim, exponentul lui plus unu.
Algoritmul distruge n, deci păstrează o copie dacă îți mai trebuie.