Descompunerea în factori primi în C++

Descompunerea în factori primi scrie un număr natural mai mare decât unu ca produs de puteri ale unor numere prime. De exemplu, 360=2³·3²·5. În algoritm păstrăm factorul și exponentul său, nu doar lista tuturor divizorilor.

Factorizarea permite calcularea numărului de divizori, verificarea pătratelor perfecte și compararea structurii aritmetice a numerelor. Aceste aplicații folosesc exponenții, de aceea este important să nu ne oprim după prima împărțire la un factor.

Cum funcționează

Încercăm candidați d în ordine crescătoare. Cât timp d divide valoarea rămasă, împărțim la d și creștem exponentul. Dacă exponentul este nenul, afișăm perechea. După eliminarea tuturor factorilor mai mici, un candidat compus nu mai poate divide restul: factorii săi primi au fost deja eliminați.

Continuăm cât timp d*d <= n, unde n este restul curent, nu neapărat numărul inițial. Folosim forma d <= n/d pentru a evita înmulțirea care ar putea depăși tipul. Dacă la final n>1, acesta este un factor prim rămas și are exponentul unu în restul curent.

Numărul unu este un produs vid de factori primi. Nu îl considerăm prim și nu inventăm factorul 1. Programul afișează convențional 1 pentru intrarea 1, fără a susține că aceasta este o putere a unui factor prim. Intrarea zero este exclusă: împărțirea repetată a lui zero nu ar micșora valoarea.

Exemplu urmărit pas cu pas

Pentru 360, împărțim la 2 de trei ori: 360,180,90,45. Înregistrăm 2³. La d=3 obținem 45,15,5, deci 3². Când restul este 5, nu mai trebuie să testăm candidați până la rădăcina numărului inițial; 5 rămâne factorul final.

Pentru 49, candidații 2 până la 6 nu divid numărul, iar 7 îl divide de două ori. Pentru un număr prim, majoritatea candidaților nu produc împărțiri, de aceea acest caz este relevant pentru timpul maxim.

Implementare C++17

#include <iostream>
int main() {
    long long n;
    std::cin >> n;
    bool first = true;
    for (long long d = 2; d <= n / d; ++d) {
        int e = 0;
        while (n % d == 0) {
            n /= d;
            ++e;
        }
        if (e) {
            if (!first)
                std::cout << ' ';
            std::cout << d << '^' << e;
            first = false;
        }
    }
    if (n > 1) {
        if (!first)
            std::cout << ' ';
        std::cout << n << "^1";
        first = false;
    }
    if (first) {
        std::cout << 1;
    }
    std::cout << '\n';
}

De ce funcționează și cât costă

În orice moment, produsul puterilor deja extrase înmulțit cu restul n este egal cu numărul inițial. Când nu mai există un divizor până la rădăcina restului, restul este prim sau unu. Astfel, nu pierdem niciun factor.

Timpul prin încercarea divizorilor este O(sqrt(N)) în cazul nefavorabil, raportat la numărul inițial N. Memoria suplimentară este O(1) când afișăm imediat factorii. Exemplul acceptă 1 <= N <= 10^12 pentru demonstrație, dar un milion de încercări trebuie raportat la limita de timp a problemei.

Greșeli frecvente

Nu compara permanent cu o limită greșită și nu uita factorul rămas după buclă. Formula numărului de divizori este produsul (e+1), nu suma exponenților. Pentru un pătrat perfect, toți exponenții trebuie să fie pari.

Exersează

Câți divizori pozitivi are 360? Este 360 pătrat perfect?

Rezolvare explicată: Exponenții sunt 3,2,1, deci numărul divizorilor este 432=24. Nu este pătrat perfect, deoarece exponenții lui 2 și 5 sunt impari.

Continuă să înveți

Numere prime, bucle și înmulțiri și tipuri.

Întrebări frecvente

De ce poate rămâne un factor după buclă?

După eliminarea factorilor mici, restul poate fi un număr prim mai mare decât limita curentă de încercare. Dacă restul depășește unu, trebuie inclus în rezultat.

Cum calculez numărul divizorilor?

Pentru fiecare factor prim cu exponent e există e+1 alegeri în construirea unui divizor. Înmulțești aceste numere pentru toți factorii primi.

Cum verific un pătrat perfect prin factorizare?

Un număr pozitiv este pătrat perfect exact când fiecare exponent din descompunerea sa este par. De exemplu, 36=2²·3² respectă condiția.

De ce nu folosim factorul unu?

Înmulțirea cu unu nu schimbă numărul și ar permite reprezentări fără sfârșit. Unu nu este număr prim și nu face parte din descompunerea în factori primi.

Când este preferabil un ciur?

Când ai multe numere dintr-un domeniu relativ mic, poți precalcula factori primi minimi. Costul inițial se distribuie atunci între numeroase factorizări.