Numărul de cifre ale factorialului unui număr

Dându-se un număr natural n, vrem să aflăm numărul de cifre ale operației n! = 1 * 2 * … * n (n factorial).

Exemple

Pentru n = 1, răspunsul este 1 (1! = 1 are o cifră).

Pentru n = 5, răspunsul este 3 (5! = 120 are trei cifre).

Pentru n = 0, răspunsul este 1 (0! = 1 are o cifră).

Algoritm naiv de aflare a numărului de cifre ale factorialului

Un algoritm naiv calculează valoarea n!, după care calculează numărul de cifre ale acestuia. Acest algoritm nu este recomandat deloc, deoarece n! crește foarte repede (13! depășește tipul de date int), iar folosirea anumitor tehnici precum numerele mari este impractică, fiind ineficientă, în special pentru valori uriașe (n = 1.000.000, spre exemplu).

Algoritm eficient de aflare a numărului de cifre ale factorialului

Vom folosi logaritmii pentru a simplifica calculul nostru. Operațiile prezentate sunt notate cu lg, reprezentând logaritmul în baza 10 a unui număr.

Proprietăți știute

În primul rând, lg(a * b) = lg(a) + lg(b).

De asemenea, [lg(x)] + 1 = numărul de cifre ale numărului x (în baza 10), unde [x] reprezintă partea întreagă a numărului x.

Algoritmul explicat

Din a doua proprietate, deducem că noi trebuie să aflăm valoarea [lg(n!)] + 1.

Așadar, ne propunem să aflăm valaorea lg(n!). Din proprietățile de mai sus găsim că lg(n!) = lg(1 * 2 * 3 * … * n) = lg(1) + lg(2) + lg(3) + … + lg(n).

Practic am redus problema la ceva rezolvabil: logaritmii numerelor se află repede, iar însumându-i și aplicând formula de mai sus, putem găsi ușor răspunsul dorit.

Rezolvare în C++

Vom asuma că numărul citit este natural (n ≥ 0).

#include <iostream>
#include <cmath>

using namespace std;

int nFactorialCifre(int x) {
    double suma = 0;
    for(int i = 1; i <= x; i++) {
        suma += log10(i);
    }
    //suma conține valoarea lg(1) + lg(2) + … + lg(n) = lg(n!)
    return floor(suma) + 1; // [lg(n!)] + 1, adică numărul de cifre ale lui n!
}

int main()
{
    int n;
    cin >> n;
    cout << nFactorialCifre(n);
    return 0;
}

Bibliografie sau alte resurse

• StackExchange
• GeeksForGeeks