Descompunerea în factori primi la BAC: algoritm C++

Descompunerea în factori primi în C++ se construiește împărțind repetat numărul la fiecare divizor găsit și numărând împărțirile exacte. Numărul de împărțiri este exponentul acelui factor. La BAC, această schemă poate apărea în cerințe despre factori distincți, exponenți, numărul divizorilor sau proprietățile unui număr natural.

Vom lucra cu numere naturale strict pozitive, de cel mult un miliard. Pentru unu, descompunerea nu conține factori primi. Zero necesită altă discuție și este exclus explicit din domeniul algoritmului prezentat. Respectarea domeniului te ajută să interpretezi corect exemplele din arhiva de subiecte BAC.

Factorul și exponentul au roluri diferite

Numărul 360 se scrie ca produsul dintre doi la puterea a treia, trei la puterea a doua și cinci la puterea întâi. Factorii primi distincți sunt doi, trei și cinci. Sunt trei factori distincți, dar șase factori dacă îi numeri cu repetiție, deoarece suma exponenților este șase.

Factor prim	Exponent	Ce înseamnă exponentul
2	3	Împărțim exact de trei ori la doi
3	2	Împărțim exact de două ori la trei
5	1	Împărțim exact o dată la cinci

Expresiile „numărul factorilor primi distincți” și „suma exponenților” cer rezultate diferite. Înainte de programare, scrie un exemplu precum acesta și decide ce informație trebuie acumulată. Confuzia dintre factor și exponent poate produce un program care rulează fără erori, dar răspunde altei întrebări.

De ce împărțim repetat

Pentru factorul doi, pornim de la 360 și obținem succesiv 180, 90 și 45. Următoarea împărțire la doi nu mai este exactă. Exponentul este trei, iar partea încă neprelucrată a numărului este 45.

Apoi încercăm factorul trei. Din 45 obținem 15, apoi cinci. Exponentul lui trei este doi. Valoarea rămasă, cinci, este factorul final. Nu revenim la numărul inițial după fiecare divizor: reducerea lui este chiar mecanismul care elimină factorii deja găsiți.

De aceea, în implementare este utilă o copie de lucru. Dacă trebuie să afișezi și numărul inițial ori să compari o proprietate cu el, îl păstrezi separat. Modificarea copiei nu trebuie să distrugă informația de care ai nevoie într-o etapă ulterioară.

Schema cu două bucle

Bucla exterioară încearcă divizorii, începând cu doi. Pentru fiecare candidat, exponentul pornește de la zero. Bucla interioară împarte copia cât timp restul este zero și mărește exponentul la fiecare împărțire.

După bucla interioară, un exponent pozitiv arată că am găsit un factor. Un exponent zero înseamnă că acel candidat nu divide valoarea curentă. Nu afișa o pereche pentru fiecare candidat încercat, fiindcă ai introduce în rezultat și numere care nu sunt factori ai numărului inițial.

Nu este obligatoriu să verifici separat primalitatea fiecărui candidat. Dacă un candidat compus ar divide copia rămasă, un factor prim mai mic al lui ar divide și acea copie. Dar factorii mai mici au fost deja eliminați complet. Astfel, candidații compuși nu vor avea exponent pozitiv în această parcurgere.

Oprirea la rădăcină și factorul rămas

Putem opri încercările când candidatul depășește rădăcina pătrată a copiei curente. Dacă acea copie este încă mai mare decât unu, ea este primă. Altfel, ar avea un divizor prim cel mult egal cu rădăcina ei, iar algoritmul ar fi continuat până la acel divizor.

Condiția din program folosește împărțirea întreagă, nu produsul candidatului cu el însuși. Pentru valori pozitive, comparația este echivalentă și evită riscul depășirii tipului la calcularea pătratului. Observă că limita se aplică valorii rămase, nu obligatoriu numărului inițial.

Program C++ complet

Programul afișează câte o pereche factor–exponent pe linie. Pentru unu, afișează un mesaj explicit, deoarece lista factorilor primi este goală.

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    if (n == 1) {
        cout << "fara factori primi";
        return 0;
    }
    long long x = n;
    for (long long d = 2; d <= x / d; ++d) {
        int e = 0;
        while (x % d == 0) {
            x /= d;
            ++e;
        }
        if (e > 0) cout << d << ' ' << e << '\n';
    }
    if (x > 1) cout << x << " 1\n";
    return 0;
}

La intrarea 360 apar perechile doi–trei, trei–doi și cinci–unu. La intrarea 49, candidatul șapte este procesat de buclă și exponentul său devine doi. La intrarea 13, bucla nu găsește niciun factor, iar instrucțiunea finală afișează factorul prim rămas cu exponentul unu.

Timpul, în cel mai nefavorabil caz al acestei implementări, este de ordinul rădăcinii pătrate a numărului inițial. Un număr prim mare obligă algoritmul să încerce mulți candidați. Memoria suplimentară este constantă, deoarece perechile sunt afișate pe măsură ce sunt găsite.

Cum obții numărul divizorilor

Din descompunerea unui număr pozitiv, fiecare divizor se formează alegând un exponent pentru fiecare factor prim. Dacă exponentul unui factor în număr este trei, în divizor poate fi zero, unu, doi sau trei: patru opțiuni.

Pentru 360, ai patru opțiuni pentru exponentul lui doi, trei opțiuni pentru exponentul lui trei și două pentru exponentul lui cinci. Produsul acestora este 24, deci numărul are 24 de divizori naturali pozitivi. Nu aduni numerele de opțiuni, fiindcă alegerea se face simultan pentru fiecare factor.

În program, un acumulator pentru numărul divizorilor pornește de la unu. Pentru fiecare exponent pozitiv, îl înmulțești cu exponentul mărit cu unu. Dacă rămâne un factor prim la final, înmulțești cu doi. Această regulă dă și pentru unu răspunsul corect: are exact un divizor pozitiv, pe el însuși.

Cum adaptezi aceeași parcurgere

Pentru numărul factorilor distincți, mărești un contor o singură dată când exponentul este pozitiv. Pentru suma exponenților, adaugi exponentul. Pentru cel mai mare factor prim, reții ultimul factor identificat, inclusiv eventuala valoare rămasă după buclă.

Un număr pozitiv este pătrat perfect exact când toți exponenții din descompunere sunt pari. Numărul unu respectă proprietatea, deși lista factorilor este goală. Nu îl elimina automat din categoria pătratelor perfecte din cauza absenței factorilor primi.

Aceste adaptări sunt mai ușor de reținut dacă legi fiecare variabilă de sensul ei matematic. Poți folosi metoda din articolul despre învățare prin înțelegere: explică de ce actualizezi un contor, înainte să memorezi instrucțiunea.

Exerciții cu verificare

Pentru 72, factorii sunt doi cu exponentul trei și trei cu exponentul doi. Are doi factori primi distincți, suma exponenților cinci și doisprezece divizori pozitivi. Produsul puterilor reconstruiește numărul inițial.

Pentru 81, apare numai factorul trei, cu exponentul patru. Numărul este pătrat perfect și are cinci divizori pozitivi. Nu confunda cei cinci divizori cu numărul factorilor primi distincți, care este unu.

Pentru 77, apar șapte și unsprezece, fiecare cu exponentul unu. Ultimul factor poate fi identificat prin verificarea copiei rămase. Dacă omiți acea instrucțiune, descompunerea va fi incompletă.

Pentru unu, lista factorilor primi este goală, suma exponenților este zero și numărul divizorilor pozitivi este unu. Acest test separă trei cerințe care seamănă în formulare, dar au inițializări diferite.

Întrebări frecvente

De ce nu măresc divizorul în bucla interioară?

Trebuie să elimini toate aparițiile aceluiași factor. Divizorul se schimbă numai după ce împărțirea nu mai este exactă. Altfel, pierzi exponentul corect.

Pot folosi algoritmul pentru zero?

Nu în forma aceasta. Zero este divizibil cu orice număr pozitiv, iar împărțirea lui repetată nu îl transformă într-o valoare care să încheie bucla. Domeniul trebuie verificat înainte de folosirea algoritmului.

Ce explic într-o justificare la BAC?

Precizează ce reprezintă copia, cum numeri exponentul și de ce factorul rămas este prim. Pentru feedback pe o rezolvare proprie, poți discuta aceste trei puncte la meditații de informatică.