Слишком большие числа для long long

Question

Есть функция factorial(n), которая находит n!:

long long factorial(int n)
{
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

А также функция factorization(n), которая находит разложение n на простые множители:

vector<long long> factorization(long long n) {
   vector<long long> p;
   for (long long d = 2; d * d <= n; ++d) {
       while (n % d == 0){
           p.push_back(d);
           n /= d;
       }
   }
   if (n > 1)
       p.push_back(n);
   return p;
}

Моя задача заключается в том, чтобы найти factorization(factorial(n)). Проблема заключается в том, что n может быть достаточно большим (до 45 включительно), например 32. Тогда 32! уже не будет вмещаться в long long.
Подскажите пожалуйста, как можно решить эту проблему?

Answer 1

Я бы работал не через vector, а через map:

map<int,int> factorFactor(int n)
{
    map<int,int> M;
    for(int m = 2; m <= n; ++m)
    {
        int d = m;
        for(int i = 2; i*i <= d; ++i)
        {
            if (d%i) continue;
            while(d%i == 0)
            {
                M[i]++;
                d /= i;
            }
        }
        if (d > 1) M[d]++;
    }
    return M;
}

Так, по-моему, удобнее...

Но, вообще говоря, можно еще проще и быстрее, если рассматривать количество вхождения простых множителей в факториал — например, для 100! число двоек равно

100/2 + 100/4 + 100/8 + 100/16 + 100/32 + 100/64 = 50+25+12+6+3+1 = 97

(деления целочисленные), то же для троек

100/3 + 100/9 + 100/27 + 100/81 = 33 + 11 + 3 + 1 = 48

(см. разложение по ссылке) и прочих простых чисел. Выбор за вами.

Answer 2

Факторизация факториала отдельная задача потому что даже у больших факториалов все множители маленькие. Их можно найти быстро, если не вычислять сам факториал (медленно) и не разлагать его на простые (чрезвычайно медленно).

Почитайте как разложить факториал на простые множители. Формула не очень ясная, код проще:

// вычисляет степень простого основания p в n!
unsigned factorial_exponent(unsigned n, unsigned p) {
    // assert(is_prime(p));
    unsigned e = 0; // n / p + n / p^2 + n / p^3 + ...
    for (unsigned t = n / p; t > 0; t /= p) {
        e += t;
    }
    return e;
}

Чтобы воспользоваться этой функцией требуется найти все простые не более n. Напрашивается решето Эратосфена:

// все простые меньшие n
void get_primes(unsigned n, std::vector<unsigned> &primes) {
    primes.clear();
    std::vector<bool> sieve(n, true);
    unsigned i = 2;
    for (; i * i < n; ++i) {
        if (sieve[i]) {
            primes.push_back(i);
            for (unsigned j = i * i; j < n; j += i) {
                sieve[j] = false;
            }
        }
    }
    for (; i < n; ++i) {
        if (sieve[i]) {
            primes.push_back(i);
        }
    }
}

Всё готово для факторизации:

struct factor_t {
    unsigned p;
    unsigned e;
};

void factorial_factorization(unsigned n, std::vector<factor_t> &factors) {
    std::vector<unsigned> primes;
    get_primes(n + 1, primes);
    factors.clear();
    for (unsigned p : primes) {
        factors.push_back({p, factorial_exponent(n, p)});
    }
}

Тест:

int main() {
    unsigned n;
    std::cin >> n;
    std::vector<factor_t> factors;
    factorial_factorization(n, factors);
    for (const factor_t &f : factors) {
        std::cout << f.p << '^' << f.e << '\n';
    }
}

$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror -O3 factorial-factorization.cpp 

$ echo 45 | ./a.out 
2^41
3^21
5^10
7^6
11^4
13^3
17^2
19^2
23^1
29^1
31^1
37^1
41^1
43^1

$ time echo 1000000000 | ./a.out | wc -l
50847534

real  0m16.632s
user  0m16.776s
sys   0m0.720s

БЛОГ НА HUSL

Слишком большие числа для long long

Ответы (2 шт):