Numărul divizorilor din factori primi, în C++

Numărul 72 are descompunerea 2³·3². Un divizor pozitiv al lui poate conține zero, unu, doi sau trei factori 2 și zero, unu sau doi factori 3. Cele 4 alegeri pentru primul exponent se combină cu cele 3 pentru al doilea: obținem 12 divizori.

De unde vine formula

Dacă n=p₁^e₁·p₂^e₂·…·pₖ^eₖ, numărul divizorilor pozitivi este (e₁+1)(e₂+1)…(eₖ+1). Exponentul zero contează: alegerea lui pentru toți factorii produce divizorul 1. Alegerea exponenților maximi produce n. Aici îi numărăm pe amândoi, spre deosebire de problemele care cer numai divizorii proprii.

Citim 1≤n≤10^9 și afișăm numărul divizorilor săi pozitivi. Pentru 1, descompunerea nu are factori primi; rezultatul este 1 deoarece singurul divizor este chiar 1. Inițializarea produsului cu 1 tratează natural acest caz.

Scoatem fiecare factor complet

Păstrăm o copie x a numărului. Pentru fiecare d posibil, împărțim repetat x la d și numărăm împărțirile. Un exponent e nenul contribuie cu factorul e+1. După ce am eliminat factorii mici, un rest x mai mare decât 1 este prim și contribuie cu 2.

Pentru 72, cele trei împărțiri la 2 lasă x=9 și înmulțesc răspunsul cu 4. Cele două împărțiri la 3 lasă x=1 și îl înmulțesc cu 3. Nu adunăm exponenții: fiecare alegere pentru 2 se poate combina cu fiecare alegere pentru 3.

Exponentul lui 2 are patru alegeri, 0,1,2,3. Exponentul lui 3 are trei alegeri, 0,1,2. Cele 4×3 combinații dau 12 divizori.Mărește schema ↗

#include <iostream>
using namespace std;
int main() {
    long long x; cin >> x;
    long long rezultat=1;
    for(long long d=2; d<=x/d; ++d) {
        int e=0;
        while(x%d==0) { x/=d; ++e; }
        if(e>0) rezultat*=e+1;
    }
    if(x>1) rezultat*=2;
    cout << rezultat << '\n';
}

Verificarea opririi

Limita folosește x, valoarea rămasă, nu n inițial. Dacă nu mai există un factor până la rădăcina lui x, acesta nu poate fi compus: un număr compus ar avea cel puțin un asemenea factor. De aceea putem încheia cu înmulțirea cu 2.

În cel mai rău caz încercăm O(√n) candidați. Această notație descrie cum crește numărul pașilor când crește n. Memoria auxiliară este constantă, O(1), deoarece nu stocăm lista divizorilor.

Exersează

Pentru 1, 13, 36 și 72 rezultatele sunt 1, 2, 9 și 12. Explică de ce pătratele perfecte au un număr impar de divizori: toți exponenții sunt pari, deci fiecare e+1 este impar. Verifică separat n=2, care ajunge direct în tratamentul restului prim.

Continuă cu factorii primi, divizorii și ciurul pentru mai multe numere.

Întrebări frecvente

Cum calculez numărul divizorilor din descompunerea în factori primi?

Dacă exponenții factorilor primi sunt e₁, e₂ și așa mai departe, înmulțește valorile e₁+1, e₂+1 etc. Pentru 72=2³·3², rezultatul este 4·3=12 divizori pozitivi.

De ce adaug 1 la fiecare exponent?

Un divizor poate conține factorul prim la oricare exponent de la zero până la exponentul din număr. Pentru exponentul 3 există patru alegeri: 0, 1, 2 și 3.

Câți divizori pozitivi are numărul 1?

Un singur divizor: 1. Produsul folosit la numărare pornește de la 1 și rămâne astfel dacă nu există factori primi. Nu confunda această problemă cu numărarea divizorilor proprii.