Поиск различных чётных натуральных делителей чисел в определённом промежутке
Нужно написать программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [125 256; 125 330], числа, имеющие ровно шесть различных чётных натуральных делителей. Для каждого найденного числа записать эти шесть делителей в шесть соседних столбцов на экране с новой строки. Делители в строке должны следовать в порядке возрастания.
Например, в диапазоне [2; 48] ровно шесть чётных различных натуральных делителей имеют числа 24, 36 и 40, поэтому для этого диапазона вывод на экране должен содержать следующие значения:
2 4 6 8 12 24
2 4 6 12 18 36
2 4 8 10 20 40
То, как я попытался решить эту задачу:
a = 125256
b = 125330
for n in range(a, b+1):
ds = []
for d in range(2, n//2+1): #честно говоря, не до конца понимаю, какую функцию выполняет здесь n//2+1
if n%d == 0:
ds.append(d)
if len(ds) > 6:
break
if len(ds) == 6:
print(ds[0], ds[1], ds[2], ds[3], ds[4], ds[5])
#по-моему, 7-я строка должна выглядеть так: if n%d == 0 and d%2 == 0:
#но тогда на экран вообще ничего не выводится
Хотелось бы услышать от людей, которые в пайтоне разбираются, что я делаю не так.
Ответы (3 шт):
for d in range(2, n//2+1): #честно говоря, не до конца понимаю, какую функцию выполняет здесь n//2+1
т.е. вы написали код и не понимаете что вы написали? или вы его списали?
ну сначала надо разобраться как вообще должен выглядеть алгоритм
если считать, что 1 не является делителем, то тогда вам надо
для каждого числа
nпройтись от числамiот 2 доnвключительно и попытаться разделить числоnнаiесли деление происходит без остатка (модуль равен 0) и делитель - четный, то +1 к кол-ву найденных делителей
for n in range(a, b + 1): count = 0 for j in range(2, n + 1): if n % j == 0 and j % 2 == 0: count += 1 if count == 6: print("нашли")
очевидно, что n для самого себя является делителем, а ближайший более маленький делитель - это n / 2, просто потому что 0 < n / (n / 2 + j) < 1
поэтому счетчик делителей можно начинать с 1 и перебирать числа только до n / 2:
единственное что вначале надо проверить а является ли n - четным
count = int(n % 2 == 0)
чтобы не делать много if else просто перевел булево значение в целочисленное
for n in range(a, b + 1):
count = int(n % 2 == 0)
for j in range(2, n // 2 + 1):
if n % j == 0 and j % 2 == 0:
count += 1
if count == 6:
print("нашли")
в данном случае
n // 2 + 1
чтобы гарантированно захватить половину числа n при переборе
Если надо вывести делители, то тогда всего лишь в код надо добавить их сбор (учесть, что 1 делитель мы знаем всегда - это n)
for n in range(a, b + 1):
count = int(n % 2 == 0)
dividers = [n] if n % 2 == 0 else []
for j in range(2, n // 2 + 1):
if n % j == 0 and j % 2 == 0:
count += 1
dividers.append(j)
if count == 6:
print(*sorted(dividers))
Ну вот такой вариант правильно проходит ваш тестовый пример:
a = 2 # 125256
b = 48 #125330
k = 0
for n in range(a, b+1, 2):
ds = []
for d in range(2, n//2 + 1, 2):
if n%d == 0:
ds.append(d)
if len(ds) > 6:
break
ds.append(n)
if len(ds) == 6:
print(n, '-', ds[0], ds[1], ds[2], ds[3], ds[4], ds[5])
Вывод:
24 - 2 4 6 8 12 24
36 - 2 4 6 12 18 36
40 - 2 4 8 10 20 40
Пояснения:
- Перебирать имеет смысл только чётные числа, у нечётных чисел не будет чётных делителей, поэтому шаг
2в цикле поn(сокращаем перебор в 2 раза) - Делители тоже имеет смысл перебирать только чётные - ведь таково условие, поэтому в цикле по
dя тоже поставил шаг2(сокращаем перебор в 2 раза) - Само число тоже считается своим делителем, судя по приведённому примеру, поэтому я его добавил в список вручную после окончания цикла. Можно это делать и до начала цикла, но тогда в списке числа получаются не по порядку, поэтому добавляю в конце, просто для красоты.
- Перебор сделан до
n//2 + 1потому, что если число чётное, значит оно делится на2, делителей меньше чем2быть не может, значит перебор имеет смысл вести только доn//2(а самоnя добавляю потом отдельно),+1же тут из-за особенностей работыrange- конечное значение не включается в перебор, поэтому надо добавить1(итого - опять же сокращаем перебор ещё в 2 раза).
Результат для чисел из самого задания:
125262 - 2 6 18 13918 41754 125262
125288 - 2 4 8 31322 62644 125288
125298 - 2 6 18 13922 41766 125298
Если править ваш код, получится следующее:
a = 125256
b = 125330
for n in range(a, b+1):
ds = []
for d in range(2, n+1): # т.к. a и b небольшие, можно рассмотреть все делители числа
if n%d == 0:
if d % 2 == 0: ds.append(d) # верно, на этом шаге проверяем, что делитель четный
# if len(ds) > 6: избыточный код, незначительно ускоряет решение
# break
if len(ds) == 6:
print(ds[0], ds[1], ds[2], ds[3], ds[4], ds[5])
Оптимальное решение такое:
- Перебираем все числа
- Каждое число делим на все числа до корня включительно.
- Каждый раз получаем два делителя (делитель и частное), если какой-то из них четный — сохраняем.
for n in range(125256, 125330 +1):
counter = set() # множество вместо списка, избегаем повторы
for d in range(1, int(n ** 0.5) + 1): # перебор до корня включительно
if n % d == d % 2 == 0: counter.add(d) # сохраняем делитель, если он четный
if n % d == n // d % 2 == 0: counter.add(n // d) # сохраняем частное (на него число тоже делится), если оно четное
if len(counter) == 6: # если делителей шесть
print(*sorted(counter)) # выводим их в порядке возрастания