Вывести все числа, у которых четная сумма всех делителей
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 шт):
у вас чрезмерно усложнен код, делает кучу лишнего, зачастую с ошибками
ведь по сути алгоритм то состоит из нескольких шагов:
пройтись по всем числам из диапазона
для каждого числа пройтись по всем возможным делителям (т.е. от 2 до самого числа включительно)
если возможный делитель действительно является делителем (число делится на него без остатка), то сложить его с ранее найденными
если сумма делителей оказалась чётной - вывести ее на экран
Все.
Остальные действия излишни
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 и числа замечательно выведет
зачем перекладывать результат из одного массива во второй, а затем из второго в третий?
Ответ
Я запустил вашу программу с 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