Вывести все числа, у которых четная сумма всех делителей

a = int(input())
b = int(input())
def sumchis(i):
    sum = 0
    d = [ x for x in range(1, i // 2 + 1) if i % x == 0 ]
    d.append(i)
    for j in d:
        sum += j
    return(sum)
def sop(a, b, sumchis):
    chet = []
    vsedel = []
    alch3 = []
    ind = []
    kon = []
    for i in range(a, b+1):
        alch3.append(i)
        ch = sumchis(i)
        vsedel.append(str(ch))
        if ch % 2 == 0:
            chet.append(str(ch))
    for q in vsedel:
        if q in chet:
            id = vsedel.index(q)
            ind.append(id)
    for ws in ind:
        seed = alch3[ws]
        kon.append(seed)
    return (kon)
print(sop(a, b, sumchis))

Не понимаю почему выводит такой результат

[3, 5, 6, 7, 10, 6, 12]

хотя должен [3, 5, 6, 7, 10, 11, 12] В чем ошибка? upd. Должно так быть, тк я сначала считаю сумму делителей каждого числа, затем беру только четные и надо вывести числа, соответствующие им. Числа должны выводиться всё время новые, а не повторяться


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

Автор решения: Zhihar

у вас чрезмерно усложнен код, делает кучу лишнего, зачастую с ошибками

ведь по сути алгоритм то состоит из нескольких шагов:

  1. пройтись по всем числам из диапазона

  2. для каждого числа пройтись по всем возможным делителям (т.е. от 2 до самого числа включительно)

  3. если возможный делитель действительно является делителем (число делится на него без остатка), то сложить его с ранее найденными

  4. если сумма делителей оказалась чётной - вывести ее на экран

Все.

Остальные действия излишни

a = int(input("Введите левую границу диапазона: "))
b = int(input("Введите левую границу диапазона: "))

for num in range(a, b + 1):
    # определить сумму делителей числа
    res = 0

    for divider in range(2, num + 1):
        if num % divider == 0:
            res += divider

    if res % 2 == 0:
        print(num, end=' ')

Вообще задачу в 1 строчку можно решить:

a = int(input("Введите левую границу диапазона: "))
b = int(input("Введите левую границу диапазона: "))

print(*[i for i in range(a, b + 1) if sum([j for j in range(2, i + 1) if i % j == 0]) % 2 == 0])

Вот у вас код находит сумму делителей:

def sumchis(i):
    sum = 0
    d = [ x for x in range(1, i // 2 + 1) if i % x == 0 ]
    d.append(i)
    for j in d:
        sum += j
    return(sum)

во-первых зачем вы считаете 1 делителем?

во-вторых зачем вы сначала формируете массив, чтобы по том по нему еще раз пройти?

в третьих зачем вы делаете цикл до середины числа i? понятно, что оптимизация скорости и вы в 2 раза скорость увеличите, но у вас не та задача, где это нужно

теперь код основной функции:

def sop(a, b, sumchis):
    chet = []
    vsedel = []
    alch3 = []
    ind = []
    kon = []
    for i in range(a, b+1):
        alch3.append(i)  # зачем
        ch = sumchis(i)
        vsedel.append(str(ch))
        if ch % 2 == 0:
            chet.append(str(ch))
    for q in vsedel:
        if q in chet:
            id = vsedel.index(q)
            ind.append(id)
    for ws in ind:
        seed = alch3[ws]
        kon.append(seed)
    return (kon)

зачем вы постоянно гоняете числа в строки? print и числа замечательно выведет

зачем перекладывать результат из одного массива во второй, а затем из второго в третий?

→ Ссылка
Автор решения: Stanislav Volodarskiy

Ответ

Я запустил вашу программу с a = 1 и b = 12 и распечатал vsedel:

['1', '3', '4', '7', '6', '12', '8', '15', '13', '18', '12', '28']

В нём два элемента со значением '12'. Один с индексом 5, второй с индексом 10. Они соответствуют числам 6 и 11. И действительно оба эти числа имеют одинаковую сумму делителей: 1 + 2 + 3 + 6 = 1 + 11 = 12.

Когда в цикле вы вызываете id = vsedel.index(q), для q = '12' оба раза отыскивается индекс 5 – первый индекс со значением '12'. Получается что число 6 затеняет число 11.

Цикл обработки vsedel можно поменять так:

    for i, q in enumerate(vsedel):
        if q in chet:
            ind.append(i)

Это решит вашу проблему.

Идём дальше

Эта странная программа решает задачу с оглядкой на теорию чисел:

import math


def is_square(n):
    isqrt = math.isqrt(n)
    return isqrt * isqrt == n


def main():
    a = int(input())
    b = int(input())

    for n in range(a, b + 1):
        if not (is_square(n) or (n % 2 == 0 and is_square(n // 2))):
            print(n)


main()
$ echo -e "1\n12" | python even_sum_of_divisors.py
3
5
6
7
10
11
12

Миллион чисел за одну секунду:

$ time -p echo -e "1\n1000000" | python even_sum_of_divisors.py | wc -l
998293
real 0.86
user 0.85
sys 0.02

Дело в том что число имеет нечётную сумму делителей только если оно имеет вид r2 или 2·r2, где r – натуральное. Необходимая теория есть в статье Функция делителей.

А можно ещё быстрее. Обратите внимание, что львиная доля всех чисел имеет чётную сумму делителей. Если придумать способ быстро строить растущую последовательность чисел с нечётной суммой делителей, все остальные можно печатать большими пачками.

Генератор odds(start) выдаёт последовательность чисел у которых нечётные суммы делителей. Последовательность начинается так: 1, 2, 4, 8, 9, 16, 18, 25, 32, 36, 49, 50, 64, 72, 81, 98, 100, 121, 128, 144, .... main печатает числа из промежутков между числами этой последовательности.

import math


def odds(start):
    i = math.isqrt( start           - 1) + 1
    j = math.isqrt((start + 1) // 2 - 1) + 1
    while True:
        if i * i < 2 * j * j:
            yield i * i
            i += 1
        else:
            yield 2 * j * j
            j += 1


def main():
    a = int(input())
    b = int(input())

    prev_n = a
    for n in odds(a):
        n = min(n, b + 1)
        for m in range(prev_n, n):
            print(m)
        if n > b:
            break
        prev_n = n + 1


main()
$ echo -e "1\n12" | python even_sum_of_divisors.py
3
5
6
7
10
11
12

Время до миллиона стало лучше:

$ time -p echo -e "1\n1000000" | python even_sum_of_divisors.py | wc -l
998293
real 0.43
user 0.44
sys 0.00

Лучше, но не намного. Почти всё время тратится на печать. Заменим печать отдельных чисел на печать интервалов:

import math


def odds(start):
    i = math.isqrt( start           - 1) + 1
    j = math.isqrt((start + 1) // 2 - 1) + 1
    while True:
        if i * i < 2 * j * j:
            yield i * i
            i += 1
        else:
            yield 2 * j * j
            j += 1


def main():
    a = int(input())
    b = int(input())

    prev_n = a
    for n in odds(a):
        n = min(n, b + 1)
        if prev_n == n - 1:
            print(prev_n)
        elif prev_n < n - 1:
            print(f'{prev_n}-{n - 1}')
        if n > b:
            break
        prev_n = n + 1


main()
$ echo -e "1\n12" | python even_sum_of_divisors.py
3
5-7
10-12

До миллиона 1698 интервалов, считается мгновенно:

$ time -p echo -e "1\n1000000" | python even_sum_of_divisors.py | wc -l
1698
real 0.04
user 0.03
sys 0.00

До ста миллиардов 539818 интервалов, считается быстрее секунды:

$ time -p echo -e "1\n100000000000" | python even_sum_of_divisors.py | wc -l
539818
real 0.64
user 0.65
sys 0.02
→ Ссылка