Project Euler 549 - Мои функции не возвращают ответ, который он должен вернуть, и я не знаю, что не так

Question

Проблема гласит следующее:

Наименьшее число m такое, что 10 делит m! м = 5.
Наименьшее число m такое, что 25 делит m! м = 10.

Пусть s (n) наименьшее число m такое, что n делит m!.

То есть s (10) = 5 и s (25) = 10.

Пусть S (n) будет ∑s (i) для 2 ≤ i ≤ n. S (100) = 2012.

Найти S (10 ^ 8).

Я сделал функцию для факториалов и функцию для s (n), которая при тестировании их работала отлично, но при тестировании моей следующей функции S (n) она возвращала 1805 в качестве ответа вместо 2012 что я должен был получить.

public class Program
{
    public static long Factorial(long i) {
            if (i <= 1)
                return 1;
            return i * Factorial(i - 1);
    }


    public static long s(long n) {
        bool dontStop = true;
        for (long i = 0; dontStop; i++) {
            if (Factorial(i)%n == 0) {
                dontStop = false;
                return i;
                break;
            }     
        }
        return 0;
    }

    public static long S(long n) {
        long count = 0;
        for (long i = 1; i <= n; i++) {
            //Console.WriteLine(count);
            count += s(i);
        }
        return count;
    }

    public static void Main(string[] args)
    {
        Console.WriteLine(S(100));
    }
}

Answer 1

Тип данных long просто не достаточно «большой» для высоких факториалов, а с высоким я имею в виду больше 20, потому что:

Console.WriteLine(Factorial(20));
Console.WriteLine(long.MaxValue);

возвращает

2432902008176640000
9223372036854775807

Как вы можете видеть, они имеют тот же порядок величины, что означает, что long не подходит даже для Factorial(21) и действительно возвращает -4249290049419214848.

Вы должны использовать System.Numerics.BigInteger, который может хранить произвольно большие целые числа.