Понятие факториала известно всем. Это функция, вычисляющая произведение последовательных натуральных чисел от 1 до N включительно: N! = 1 \* 2 \* 3 \*… \* N. Факториал — быстрорастущая функция, уже для небольших значений N значение N! имеет много значащих цифр. Попробуем реализовать эту функцию на языке программирования. Очевидно, нам понадобиться язык, поддерживающий длинную арифметику. Я воспользуюсь C#, но с таким же успехом можно взять Java или Python. Итак, простейшая реализация (назовем ее наивной) получается прямо из определения факториала:

static BigInteger FactNaive(int n)
{
BigInteger r = 1;
for (int i = 2; i <= n; ++i)
r *= i;
return r;
}


На моей машине эта реализация работает примерно 1,7 секунд для N=50000. Далее я покажу два алгоритма, которые работают более чем в два раза быстрее наивной реализации. [Читать дальше →][1]

[1]: http://habrahabr.ru/post/255761/#habracut