Задача на теорию чисел (python)

Question

Задача звучит следующим образом.

По заданному натуральному числу N необходимо вычислить количество натуральных чисел, которые являются делителями N! (факториала числа N). Например, при N=4, N!=4⋅3⋅2⋅1=24. Это число имеет следующие делители: 1,2,3,4,6,8,12,24. Таким образом, искомое количество составляет 8. Напишите программу, которая по натуральному N находит количество делителей его факториала.

Вот мой код.

import math

def primfacs(n):
   i = 2
   primfac = []
   while i * i <= n:
       while n % i == 0:
           primfac.append(int(i))
           n = n / i
       i += 1
   if n > 1:
       primfac.append(int(n))
   return primfac

number = int(input())
new_number = math.factorial(number)
primfac = sorted(primfacs(new_number))
data = []
for fac in primfac:
    if fac not in data:
        data.append(fac)
    else:
        continue
print(len(data))

Получаю неверный ответ на одном из тестов (значения неизвестны).

Answer 1

Решение нашел. Привожу код.

from math import factorial

def factor(n):
    res = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            res.append(i)
            n //= i
        else:
            i += 1
    if n > 1:
        res.append(n)
    return res

n = int(input())
if n == 1:
    print(1)
else:
    primes = factor(factorial(n))
    answer, num, actual, length = 1, 1, primes[0], len(primes)
    for i in range(1, length):
        if primes[i] == actual:
            num += 1
        else:
            answer *= num + 1
            num = 1
            actual = primes[i]
    answer *= num + 1
    print(answer)

БЛОГ НА HUSL

Задача на теорию чисел (python)

Ответы (1 шт):