Факторизация факториала отдельная задача потому что даже у больших факториалов все множители маленькие. Их можно найти быстро, если не вычислять сам факториал (медленно) и не разлагать его на простые (чрезвычайно медленно).
Почитайте как разложить факториал на простые множители. Формула не очень ясная, код проще:
// вычисляет степень простого основания 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