Определить на сколько нулей оканчивается n!

@nononef · Регистрация: 06.03.2021

Студворк — интернет-сервис помощи студентам

Требуется написать программу на C++

Нули факториала

Найти, на сколько нулей оканчивается n! = 1 * 2 * 3 * … * n. n ≤ 1000.

Пример
Ввод Вывод
25 6

IGPIGP · 06.03.2021, 10:53

nononef, я насчитал только 5 штук:
10
20
2,5//четным числом может быть любое из доступных и я выбираю по порядку - 2,4,6
4,15
6,25
Эти числа и комбинации дают завершающий ноль от участия в общем произведении. Откуда ещё один?

@TheCalligrapher · 06.03.2021, 11:33

Сообщение от nononef

Найти, на сколько нулей оканчивается n! = 1 * 2 * 3 * … * n. n ≤ 1000.

Количество нулей будет равно количеству пар простых множителей 2 и 5 в факториальном произведении. Каждая такая пара даст дополнителный 0 в результате. Множителей 5 будет меньше, чем множителей 2, поэтому количество таких пар будет определяться именно количеством множителей 5.

А количество множителей 5 в произведении равно n/5 + n/25 + n/125 + n/625 +.... Это т.наз. формула Лежандра.

Например, для n=26 получаем 26/5 + 26/25 = 6.

Добавлено через 3 минуты

Сообщение от IGPIGP

Откуда ещё один?

В числе 25 спрятаны две пятерки, а не одна. Если для них подыскать две свободных двойки, то мы получим сразу два нуля. Например, 8*25.

Байт · 06.03.2021, 12:03

Сообщение от IGPIGP

Откуда ещё один?

25 хочет 2=х четных, А 125 еще жаднее - ему 3 подавай.
И двоек всегда хватает, только пятерки в дефиците

@Volga_ · 06.03.2021, 12:09

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
int num5(int i)
{
    int n = 0;
    while (i % 5 == 0 && i > 0)
    {
        n += 1;
        i = i / 5;
    }
    return n;
}
int main() 
{
    int n;
    cin >> n;
    int num = 0;
    for (int i = 1; i <= n; i++)
    {
        num += num5(i);
    }
    cout << num;
    return 0;
}

Байт · 06.03.2021, 12:13

Любопытно было было бы обобщить на другие системы счисления. С другим основанием. Скажем 12.

IGPIGP · 06.03.2021, 12:16

Сообщение от Байт

25 хочет 2=х четных

Ч-черт... Там две простых пятерки и каждая ест одно чётное? Нужно переварить...
Но если 25 умножить на 2 то 50 (кратность 5 сохранилась и это претензия на поедание ещё одной чётной порции?). То есть каждой 5ⁿ подавай 2ⁿ... Для 25 нужно 4 и произведение даёт 2 нуля (100!!).
Теперь понятно)

@TheCalligrapher · 13.05.2022, 06:18

Сообщение от Байт

Любопытно было было бы обобщить на другие системы счисления. С другим основанием. Скажем 12.

Общее количество нулей в факториале

Байт · 13.05.2022, 14:18

Довольно быстренько получается

C++
1
2
3
4
5
6
int count0 = 0;
int five = 5;
while(n >5) {
 count0 += n/five;
  five *=5;
}

Croessmah · 13.05.2022, 15:04

Сообщение от Байт

Довольно быстренько получается

Цикл бесконечный?

Байт · 13.05.2022, 21:23

Сообщение от Croessmah

Цикл бесконечный?

Да, ошибочка моя

C++
1
2
3
4
5
6
int count0 = 0;
int five = 5;
while(n >5) {
 count0 += n/five;
  n /=5;
}

@TheCalligrapher · 13.05.2022, 22:06

Сообщение от Байт

Да, ошибочка моя

C++
1
2
3
4
5
6
int count0 = 0;
int five = 5;
while(n >5) {
 count0 += n/five;
  n /=5;
}

Теперь непонятно, почему везде прописана явная 5, а в одном месте - некая five. Какое же, интересно, значение содержит это энигматичное five... Вертится на языке догадка, но никак не могу ухватить ее за хвост.

---

Также: код содержит ошибку. 25! имеет 6 нулей на конце. А этот код говорит, что 5.

@QueryMonkey · 13.05.2022, 22:12

Байт, > Любопытно было было бы обобщить на другие системы счисления. С другим основанием. Скажем 12.

Для 12 (3*2*2) число двоек обгоняет число трек, поэтому ответ

n/3+n/9+n/27...

Попробуйте с основанием 60

@alexu_007 · 13.05.2022, 23:38

В 1000! 249 нулей.

@QueryMonkey · 13.05.2022, 23:42

alexu_007, и это только справа

@TheCalligrapher · 14.05.2022, 01:04

Сообщение от QueryMonkey

Для 12 (3*2*2) число двоек обгоняет число трек, поэтому ответ
n/3+n/9+n/27...

Неправильно. Для нас важно число пар двоек. А вот оно уже не обязательно обгоняет число троек.

Алгоритм я приводил по ссылке. Контрпример там же: 99!₁₂ имеет 47 нулей на конце, а по вашей формуле получается 48.

Сообщение от QueryMonkey

Попробуйте с основанием 60

60 = 2² * 3 * 5

Формула Лежандра для 2, делим результат на 2
(Формула Лежандра для 3 - не нужно)
Формула Лежандра для 5

Выбираем минимум.

Добавлено через 4 минуты
---

Тут, видимо, проглядывает еще одна оптимизация (не уверен, что всегда правильная):

Факторизация 60 содержит 2² и 5. Так как 2*2 < 5, то ясно, что минимум будет достигаться на 5.
Факторизация 12 тоже содержит 2², но не содержит факторов больших чем 2*2, поэтому такую оптимизацию применить невозможно. Для 12 контрпримеров много.

Другими словами, определим

$https://www.cyberforum.ru/cgi-bin/latex.cgi?L(x, p) = \left[ \frac{x}{{p}^{1}}\right] + \left[ \frac{x}{{{p}}^{2}}\right] + \left[ \frac{x}{{{p}}^{3}}\right] + ...$

Можно ли тогда утверждать, что для любого x справедливо

$https://www.cyberforum.ru/cgi-bin/latex.cgi?a * b < c \;\;\Rightarrow\;\; \frac {L(x, a)}{b} \geq L(x, c)$

Все на натуральных числах, разумеется.

@QueryMonkey · 14.05.2022, 06:30

Да, вы правы. Алгоритм не посмотрел, думал что словил.

Я правильно понимаю, что число пар двоек начинает нестрого обгонять после числа 3, поэтому следует вычесть единицу?

-1 +n/3 +n/9 +...

Ошибки на единицу, теперь не только в программировании.

@TheCalligrapher · 14.05.2022, 08:47

Сообщение от QueryMonkey

Я правильно понимаю, что число пар двоек начинает нестрого обгонять после числа 3, поэтому следует вычесть единицу?

Судя по моим вычислительным экспериментам, "обгоняние" (т.е. минимум, достигающийся на парах двоек), может быть сколько угодно большим, а не только на единицу

Например уже для 27 (27!₁₂ = b4b8026182aa54600000000000):

27/2 + 27/4 + 27/8 + 27/16 = 23 => 11 пар двоек
27/3 + 27/9 + 27/27 = 13 троек

То есть разница уже на 2.

243 дает разницу на 3.
2943 дает разницу на 4.
20415 дает разницу на 5.
63423 дает разницу на 6.

И т.д.

@QueryMonkey · 14.05.2022, 08:51

Теперь вижу, спасибо.

Л3 растет быстрее чем Л2/2? Завтра с утра посмотрю с карандашом

Байт · 14.05.2022, 11:35

C++
1
2
3
4
5
6
int count0 = 0;
int five = 5;
while(n >=five) {
 count0 += n/five;
  n /=five;
}

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@nononef 0 / 0 / 0 Регистрация: 06.03.2021 Сообщений: 1

	Определить на сколько нулей оканчивается n! 06.03.2021, 00:58. Показов 7898. Ответов 22 Метки программирование на си (Все метки) Требуется написать программу на C++ Нули факториала Найти, на сколько нулей оканчивается n! = 1 * 2 * 3 * … * n. n ≤ 1000. Пример Ввод Вывод 25 6 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 9005 / 4706 / 630 Регистрация: 04.12.2011 Сообщений: 14,003 Записей в блоге: 16
	06.03.2021, 10:53
	nononef, я насчитал только 5 штук: 10 20 2,5//четным числом может быть любое из доступных и я выбираю по порядку - 2,4,6 4,15 6,25 Эти числа и комбинации дают завершающий ноль от участия в общем произведении. Откуда ещё один? 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	06.03.2021, 12:13
	Любопытно было было бы обобщить на другие системы счисления. С другим основанием. Скажем 12. 2

@QueryMonkey Нарушающий 417 / 305 / 46 Регистрация: 13.04.2022 Сообщений: 1,759
	13.05.2022, 22:12
	Байт, > Любопытно было было бы обобщить на другие системы счисления. С другим основанием. Скажем 12. Для 12 (322) число двоек обгоняет число трек, поэтому ответ n/3+n/9+n/27... Попробуйте с основанием 60 0

@alexu_007 736 / 700 / 110 Регистрация: 29.05.2015 Сообщений: 4,267
	13.05.2022, 23:38
	В 1000! 249 нулей. 0

@QueryMonkey Нарушающий 417 / 305 / 46 Регистрация: 13.04.2022 Сообщений: 1,759
	13.05.2022, 23:42
	alexu_007, и это только справа 0

@QueryMonkey Нарушающий 417 / 305 / 46 Регистрация: 13.04.2022 Сообщений: 1,759
	14.05.2022, 06:30
	Да, вы правы. Алгоритм не посмотрел, думал что словил. Я правильно понимаю, что число пар двоек начинает нестрого обгонять после числа 3, поэтому следует вычесть единицу? -1 +n/3 +n/9 +... Ошибки на единицу, теперь не только в программировании. 0

@QueryMonkey Нарушающий 417 / 305 / 46 Регистрация: 13.04.2022 Сообщений: 1,759
	14.05.2022, 08:51
	Теперь вижу, спасибо. Л3 растет быстрее чем Л2/2? Завтра с утра посмотрю с карандашом 0

Определить на сколько нулей оканчивается n!

Решение