Кількість нулів у кінці факторіала#123
Увійти

Кількість нулів у кінці факторіала (Розбір)

Факторіал числа дорівнює добутку чисел від до . Нуль в кінці добутку з’являється в результаті перемноження і . Але оскільки при розкладі на прості множники числа двійок більше ніж п’ятірок, то кількість нулів в кінці дорівнює кількості п’ятірок в розкладі на прості множники. Кількість цих п’ятірок дорівнює

\left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{5^2} \right\rfloor + \left\lfloor \frac{n}{5^3} \right\rfloor + ...

Суми відбуваються до тих пір, поки черговий доданок не стане рівним .

Приклад

Знайдемо кількість нулів, якими закінчується

\left\lfloor \frac{100}{5} \right\rfloor + \left\lfloor \frac{100}{5^2} \right\rfloor + \left\lfloor \frac{100}{5^3} \right\rfloor + ... = 20 + 4 = 24

Третій доданок вже дорівнює нулю, так як 100 < 5^3 = 125.

Реалізація алгоритму

Читаємо значення .

scanf("%d",&n);

Вичислюємо по формулі відповідь .

res = 0;
while(n > 0)
{
  n /= 5;
  res += n;
}

Виводимо кількість нулів в кінці 

printf("%d\n",res);

Java реалізація

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);    
    int n = con.nextInt();
    int res = 0;
    while (n > 0)
    {
      n /= 5;
      res += n;
    }
    System.out.println(res);
    con.close();
  }
}
Java

Python реалізація

Читаємо значення .

n = int(input())

Вичислюємо по формулі відповідь .

res = 0
while n > 0:
  n = n // 5
  res += n

Виводимо кількість нулів в кінці 

print(res)