Количество всех натуральных делителей натурального числа n

Question

Числовые функции
Количество всех натуральных делителей натурального числа n обозначается σ0(n). Сумма всех натуральных делителей числа n обозначается σ1(n).

Ввод 6 Вывод 4 12.

Вот мой код:

x = int(input())
a = 0
d = 2 
s = int(x/2) + 1

for i in range(2, s): 
    if x % i == 0:
        d += 1
        a += i

print(d, x + 1 + a)

Пишет, что программа выполнялась долго и была прервана. Можете помочь улучшить код, чтобы он проходил по времени?

Answer 1

Если n - делитель числа x, то и x/n тоже делитель числа x.

Пример для наглядности: 2 - делитель числа 18. Поэтому и 9 (=18/2) - тоже делитель числа 18.

Таким образом, найдя один делитель, мы находим сразу два. Диапазон поиска сокращается с x/2, до sqrt(x) (для наглядности: в случае x=10000 это означает сокращение в 50 раз).

Так что примерно так:

s = int(math.sqrt(x)) + 1

for i in range(2, s):
    if x % i == 0:
        d += 2
        a = a + i + x/i

Answer 2

import math

n = int(input())

s = 0
c = 0

for i in range(1, int(math.sqrt(n))+1):
    if n%i == 0 and i!=math.sqrt(n):
        c+=2
        s+=(i+n/i)
    elif i == math.sqrt(n) and n%i == 0:
        c+=1
        s+=i

print(c, int(s))

Этот код прошёл проверку на Сириусе, пользуйся ;)

Answer 3

Функция делителей σ_x(n) вычисляется по разложению на простые:

import math


def factors(n):
    if n % 2 == 0:
        e = 0
        while n % 2 == 0:
            n //= 2
            e += 1
        yield 2, e

    i = 3

    n_sqrt = math.isqrt(n)
    while i <= n_sqrt:
        if n % i == 0:
            e = 0
            while n % i == 0:
                n //= i
                e += 1
            yield i, e
            n_sqrt = math.isqrt(n)
        i += 2

    if n > 1:
        yield n, 1


def sigma(n):
    c = 1
    s = 1
    for p, e in factors(n):
        c *= e + 1

        t = 1
        f = 1
        for _ in range(e):
            t *= p
            f += t
        s *= f
    return c, s


print(*sigma(int(input())))

БЛОГ НА HUSL

Количество всех натуральных делителей натурального числа n

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