c# - 阶乘末尾的零数

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);
    }
}

我知道我可以使用 for 循环 并除以 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

最简单的代码(在 big 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;
    
    ...
  }