напишите программу которая будет вычислять факториал 100000 выводить его и то сколько нулей в конце этого факториала, программа должна выполняться быстрее чем за 90 секунд
100000! содержит "всего" 456574 цифр, так что по крайней мере имеет смысл попытаться начать решать задачу.
Вот наивный алгоритм, который вычисляет факториал по определению (n! = 1 * 2 * 3 * ... * n):
Код (Python 3):
prod = 1
for i in range(1, 100000 + 1):
prod *= i
Количество нулей в конце в числе prod можно найти, например, так (результат находится в переменной count):
Код (Python 3):
count = 0
while prod % 10 == 0:
count += 1
prod //= 10
Наконец, проверим, сколько времени считался результат. Импортируем из модуля time функцию perf_counter, запустим её в начале программы и в конце. Разность результатов - время работы программы в секундах.
Итого получаем такую программу:
Код (Python 3):
from time import perf_counter
start = perf_counter()
prod = 1
for i in range(1, 100000 + 1):
prod *= i
print(prod)
count = 0
while prod % 10 == 0:
count += 1
prod //= 10
print(count)
end = perf_counter()
print(end - start)
Вывод полностью приводить не буду, скажу только, что вычисление на моём компьютере заняло меньше 15 секунд.
Answers & Comments
Verified answer
100000! содержит "всего" 456574 цифр, так что по крайней мере имеет смысл попытаться начать решать задачу.
Вот наивный алгоритм, который вычисляет факториал по определению (n! = 1 * 2 * 3 * ... * n):
Код (Python 3):
prod = 1
for i in range(1, 100000 + 1):
prod *= i
Количество нулей в конце в числе prod можно найти, например, так (результат находится в переменной count):
Код (Python 3):
count = 0
while prod % 10 == 0:
count += 1
prod //= 10
Наконец, проверим, сколько времени считался результат. Импортируем из модуля time функцию perf_counter, запустим её в начале программы и в конце. Разность результатов - время работы программы в секундах.
Итого получаем такую программу:
Код (Python 3):
from time import perf_counter
start = perf_counter()
prod = 1
for i in range(1, 100000 + 1):
prod *= i
print(prod)
count = 0
while prod % 10 == 0:
count += 1
prod //= 10
print(count)
end = perf_counter()
print(end - start)
Вывод полностью приводить не буду, скажу только, что вычисление на моём компьютере заняло меньше 15 секунд.