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

Question

Числовые функции
Количество всех натуральных делителей натурального числа n обозначается σ₀(n). Сумма всех натуральных делителей числа n обозначается σ₁(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)

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

Количество - см. https://ru.stackoverflow.com/a/562360/195342 — Harry, Jun 11 '20 at 05:38

score 2 · Accepted Answer · answered Jun 12 '20 at 12:14

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))

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

answered Jun 12 '20 at 12:14

Владимир Панк-Рокер

36
2

1

Этот код можно упростить. – Эникейщик Jun 12 '20 at 12:27

Эникейщик · Answer 2 · 2020-06-10T21:10:07.273

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

edited Jun 10 '20 at 21:10

answered Jun 10 '20 at 19:37

Эникейщик

26,625

Скажите, пожалуйста, а что это за x такой? Чему он равен? Так же программа ругается на math. Нужно подключить import math? – fox_price Jun 10 '20 at 19:55
Тот же самый х, что и в вашем коде. Да, надо произвести import math. – Эникейщик Jun 10 '20 at 20:01
Выводить нужно d и a, так? Только опять же "ругается" на a и d. – fox_price Jun 10 '20 at 20:07
Замените моим кодом соответствующий фрагмент в вашем коде. – Эникейщик Jun 10 '20 at 20:40
Простите, что так мучаю вас... import math x = int(input()) a = 0 d = 2 s = int(math.sqrt(x/2)) + 1 for i in range(2, s): if x % i == 0: d =d+ 2 a = a + i + x/i print(d, x + 1 + a)
Выводит 2 и 7. Получается d не считается и с а что-то..
– fox_price Jun 10 '20 at 20:53
Исправил. Нужно брать корень от х, а у меня было от х/2, не поправил после копирования. – Эникейщик Jun 10 '20 at 21:11
Пишет, что ответ не правильный(скорее всего у 10000). Мне кажется, что это из-за а. Может не надо в конце к а прибавлять x? – fox_price Jun 10 '20 at 21:32
Мне открылась подсказка у этого задания У каждого делителя d числа n, который меньше √n есть парный ему, равный n/d, больший √n. Будем учитывать их парами. Еще нужно не забыть, что если √n является делителем, то у него нет пары. – fox_price Jun 10 '20 at 21:43
Надел в конце проверить - если число точный квадрат, то их а вычесть единицу. – Эникейщик Jun 11 '20 at 06:50
можете помочь кодом? – fox_price Jun 11 '20 at 19:11

score 0 · Answer 3 · answered Mar 26 '24 at 12:08

Функция делителей σ_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 &lt;= 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 &gt; 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())))

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

3 Answers3