Факториал числа n — это произведение всех натуральных чисел от единицы до n. Обозначается факториал символом восклицательного знака: !

Например:

$5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120$

$10!=3628800$

$20!=2432902008176640000$

Как видно из этих примеров, с увеличением аргумента, функция очень быстро растет. Если написать простую программу на C++, которая будет считать факториал произвольного числа, то мы очень быстро упремся в максимально возможное значение переменной.

Например, такая программа (1):

#include <iostream>
#include <stdint.h>

int main()
{
  // Число n, факториал которого нужно найти
  int64_t n = 20;

  // Инициализируем переменную fact значением 1
  int64_t fact = 1;

  // Цикл вычисления факториала
  for (int64_t i = 1; i <= n; i++) {
    fact = fact * i;
  }

  // Выводим факториал n
  std::cout << "Факториал " << n << " = " << fact << std::endl;

  // Выход
  return 0;
}

посчитает факториал любого натурального числа до 20, но не больше. Попытка задать большее число приведет к переполнению переменной fact и результат будет не верным. И это при том, что мы использовали тип переменной с самым большим доступным диапазоном значений int64_t.

---

Для того чтобы продвинуться дальше, нужно использовать так называемую длинную арифметику. Суть ее, если упрощенно, заключается в представлении числа, которое хранилось в переменной fact в виде массива данных, каждый элемент которого будет хранить одну десятичную цифру этого числа. Например, для хранения значения, равного 20! нам потребуется массив из 19 элементов типа char:

Индекс	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
Значение	2	4	3	2	9	0	2	0	0	8	1	7	6	6	4	0	0	0	0

Этот массив можно сделать и длиннее, например 10000 элементов, а для чисел меньше 10000 знаков заполнять неиспользуемые элементы нулями. На этом принципе основана следующая программа (2):

#include <iostream>

int main()
{
  // Число n, факториал которого нужно найти
  int n = 1000;
  int i, j = 1, r, w, l = 1;
  char fact[10000] = {0};

  // Инициализируем переменную fact значением 1
  fact[0] = 1;

  // Цикл вычисления факториала
  while (j <= n)
  {
    i = 0;
    r = 0;
    while (i < l || r > 0)
    {
      w = fact[i] * j + r;
      r = w / 10;
      fact[i] = w % 10;
      if (i == l) l++;
      i++;
    }
    j++;
  }

  // Выводим факториал n
  std::cout << "Факториал " << n << " = ";
  for (int i = l - 1; i >= 0; i--)
    std::cout << (int)fact[i];
  std::cout << std::endl;

  // Выход
  return 0;
}

С ее помощью уже можно вычислить факториал достаточно больших чисел, если выделить под хранение результата достаточно памяти. По сути верхнего предела у нее нет, как у предыдущей программы, просто если задать слишком большое число n, например 1000000, то эта программа будет очень долго выполняться. То есть мы упираемся уже не в переполнение, а во время вычисления.

---

Для того чтобы продвинуться еще дальше, то есть преодолеть этот временной барьер, нужно применять сторонние библиотеки для работы с длинной арифметикой, например GMP (GNU Multi-Precision Library). Это очень крутая библиотека для научных вычислений, она сокращает время вычисления факториала в несколько тысяч раз по сравнению с программой (2). Так, например если считать факториал для n=1000000 программой (2) на процессоре Intel Core i5 6400, то это займет около часа, а если с помощью библиотеки GMP, то несколько секунд. Причем с увеличением n отсавание будет только расти. Вот пример простой программы (3), которая вычисляет факториал 1000000 за короткое время:

#include <gmp.h>

int main()
{
  // Число n, факториал которого нужно найти
  int n = 1000000;

  // В переменной fact будет храниться результат вычисления
  mpz_t fact;
  mpz_init(fact);

  // Вычисление факториала
  mpz_fac_ui(fact, n);

  // Выводим факториал n в файл с именем 1000000.txt в текущей папке
  FILE *pFile = fopen("1000000.txt", "w");
  mpz_out_str(pFile, 10, fact);
  fclose(pFile);

  // Освобождение памяти
  mpz_clear(fact);

  // Выход
  return 0;
}

Библиотеку GMP можно скачать в виде исходников на сайте https://gmplib.org (в России нужен VPN). Процесс компиляции исходников описан на сайте. Также там есть документация по ее функциям, таким как mpz_fac_ui, которая вычисляет факториал.

В среде Linux эту библиотеку можно установить в готовом виде, выполнив команду:
  sudo apt-get install libgmp-dev (для Ubuntu)
  sudo pacman -S gmp (для Arch)

Для Windows есть окружение MSYS2 (сайт: https://www.msys2.org), в котором можно работать почти как в Linux. GMP в нем устанавливается командой:
  pacman -S mingw-w64-x86_64-gmp

Также есть версия GMP для Microsoft Visual Studio. Ее можно установить через пакетный менеджер vcpkg командой:
  vcpkg install gmp

Понятно, что можно задать гораздо большее значение n. Его можно увеличивать пока на компьютере хватает оперативной памяти. Так, например, если задать значение n=1000000000, то потребуется 32Гб оперативной памяти для успешного завершения расчета. При этом по времени это займет около 1 часа на более-менее современном процессоре. Верхней границей можно считать значение n=4294967295, т.к. второй параметр функции mpz_fac_ui не может быть больше этого числа. Правда для этого потребуется уже минимум 192Гб оперативной памяти и примерно 5 часов времени.

Также надо отметить, что для больших n, когда объем занимаемой расчетом оперативной памяти приближается к максимально доступному в системе ОЗУ, необходимо запускать программу на Linux. Дело в том, что из-за некоторых особенностей библиотеки GMP на Windows расчет будет сваливаться с ошибкой нехватки оперативной памяти, даже если свободная память в системе еще есть. А на Linux такой проблемы нет, расчет будет успешно завершен, даже если объем доступной памяти будет немного превышен.