阶乘末尾的零个数

Question

我需要找到阶乘数末尾的零的数量。这是我的代码，但它不太有效：/

using System;

class Sum
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        long factoriel = 1;

        for (int i = 1; i <= n; i++)
        {
            factoriel *= i;
        }

        Console.WriteLine(factoriel);

        int timesZero = 0;

        while(factoriel % 10 != 0)
        {
            timesZero++;
        }
        Console.WriteLine(timesZero);
    }
}

我知道我可以使用 afor loop除以 5，但我不想这样做。我的代码中的问题出在哪里以及为什么它不起作用？

Answer 1

您的算法有问题：整数溢出。想象一下，你被赋予了

  n = 1000

所以n! = 4.0238...e2567; 你不应该计算n! 但计算其形式为其中(5**p)*m和p是m一些整数的项：

  5 * m gives you one zero
 25 * m gives you two zeros
625 * m gives you three zeros etc

最简单的代码（在大n上很慢）是

  static void Main(string[] args) {
    ...
    int timesZero = 0;
    
    for (int i = 5; i <= n; i += 5) {
      int term = i;
    
      while ((term % 5) == 0) {
        timesZero += 1;
        term /= 5;
      }
    }
    ...
  }

实施速度要快得多

  static void Main(string[] args) {
    ...
    int timesZero = 0;
    
    for (int power5 = 5; power5 <= n; power5 *= 5) 
      timesZero += n / power5;
    
    ...
  }