Подсчитайте количество натуральных делителей числа x (включая 1 и само число; x≤2∗109 )

Question

Я написал код

x = int(input())
count = 0
for i in range(1, x+1):
    if x % i == 0:
        count += 1

print(count)

Но система говорит, что он не достаточно красив хотя он и работает:( Уважаемые профи, подскажите, что я забыл?

Answer 1

Количество делителей числа равно произведению степеней его простых делителей, к каждой из которых прибавлена единица. Т.е., например, для числа

12! =  
479001600 =  
2*3*4*5*6*7*8*9*10*11*12 =  
2*3*2*2*5*2*3*7*2*2*2*3*3*2*5*11*2*2*3 =  
2**10 * 3**5 * 5**2 * 7**1 * 11**1

Количество делителей будет

(10+1) * (5+1) * (2+1) * (1+1) * (1+1) = 792

Факторизация числа даже самым топорным способом займет куда меньше времени чем полный перебор.

def factorize(n):
    k = 2

    while k * k <= n:
        while n % k == 0:
            yield k
            n //= k

        k += 1

    if n > 1:
        yield n

>>> import math
>>> list(factorize(math.factorial(12)))
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 5, 5, 7, 11]

Дальше получить степени при простых делителях уже дело техники

>>> import itertools
>>> [len(g) for _, [*g] in itertools.groupby(factorize(math.factorial(12)))]
[10, 5, 2, 1, 1]

БЛОГ НА HUSL

Подсчитайте количество натуральных делителей числа x (включая 1 и само число; x≤2∗109 )

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