0

Делители факториала По заданному натуральному числу N необходимо вычислить количество натуральных чисел, которые есть делителями N! (факториала числа N).

Например, при N=4, N!=4⋅3⋅2⋅1=24. Это число имеет следующие делители: 1,2,3,4,6,8,12,24. Таким образом, искомое количество составляет 8.

Напишите программу, которая по натуральному N, находит количество делителей его факториала.

Формат входных данных

Единственная строка входного файла содержит одно целое число N(1≤N≤45).

Формат выходных данных

Единственная строка выходного файла должна содержать одно целое число — найденное количество делителей числа N! Примеры: Ввод 4 Вывод 8 Пишет, что программа выполняется слишком долго. Bот мой код:

x = int(input())
n = 1
while x > 0:
    n *= x
    x -= 1
a = []
k = 1
s = 0
while k * k <= n:
    if n % k == 0:
        a.append(k)
        if n // k != k:
            a.append(n // k)
    k += 1
print(len(a))
7
  • Нужно просто перемножить числа от 1 до N во всех комбинациях, и посчитать количество разных результатов, а не делать перебор на 100500 чисел. 10 июн 2020 в 4:19
  • В 30! больше 30 знаков. Если перебором считать, то до пенсии вряд ли успеешь. 10 июн 2020 в 4:22
  • используйте c++ 10 июн 2020 в 4:39
  • @VladislavTikhomirov сколько займёт перебор 10^30 чисел? 10 июн 2020 в 4:46
  • 2
    Следует получить разложение факториала на простые множители, после чего посчитать произведение инкрементированных количеств. Для показанного примера Например, при N=4, N!=4⋅3⋅2⋅1=24 - 4! = 2^3 * 3^1, соответственно ответ (3+1)*(1+1)=4*2=8.
    – Akina
    10 июн 2020 в 4:47

1 ответ 1

0
n=int(input())
x=1
for i in range(n):
    x=x*i
a=[]
z=0
for j in range(x):
    if x%j==0:
        a[z]=j
        z+=1
print(*a)

Я не ускорил твой код, но написал свой, надеюсь он вписывается по времени.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.