1

Числовые функции
Количество всех натуральных делителей натурального числа 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)

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

1

3 ответа 3

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

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

1
  • 1
    Этот код можно упростить. Commented 12 июн. 2020 в 12:27
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
10
  • Скажите, пожалуйста, а что это за x такой? Чему он равен? Так же программа ругается на math. Нужно подключить import math?
    – fox_price
    Commented 10 июн. 2020 в 19:55
  • Тот же самый х, что и в вашем коде. Да, надо произвести import math. Commented 10 июн. 2020 в 20:01
  • Выводить нужно d и a, так? Только опять же "ругается" на a и d.
    – fox_price
    Commented 10 июн. 2020 в 20:07
  • Замените моим кодом соответствующий фрагмент в вашем коде. Commented 10 июн. 2020 в 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
    Commented 10 июн. 2020 в 20:53
0

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

import math


def factors(n):

    if n % 2 == 0:
        # remove 2 from n
        n //= 2
        e = 1
        while n % 2 == 0:
            n //= 2
            e += 1

        yield 2, e

    p = 1 # 1, odd prime divisors of n
    while n > 1:
        # get next prime divisor of n, >= p + 2
        g = (d for d in range(p + 2, math.isqrt(n) + 1, 2) if n % d == 0)
        p = next(g, n)

        # remove p from n
        n //= p
        e = 1
        while n % p == 0:
            n //= p
            e += 1

        yield p, e


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


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

Ваш ответ

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

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