Задание №25 — Проверка делимости
Пусть М - разность максимального и минимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение М равным 0.
Напишите программу, которая перебирает целые числа, большие 860000, в порядке возрастания и ищет среди них такие, для которых значение М оканчивается на 30. Вывести первые пять найденных чисел и соответствующие им значения М.
Формат вывода: для каждого из пяти найденных чисел в отдельной строке сначала выводится само число, затем значение М. Строки выводятся в порядке возрастания найденных чисел.
Например, для числа 20 М = 10 - 2 = 8.
Правильный ответ
860064 430030 860199 286730 860264 430130 860464 430230 860499 286830
Пояснение
Решение:
У целого числа наименьший делитель, отличный от единицы, — это его наименьший простой делитель . Ему в пару идёт наибольший делитель, отличный от самого числа, равный . Значит, оба «крайних» делителя находятся за один проход: достаточно перебрать от 2 до и остановиться на первом, который делит . Если такого нет, число простое, промежуточных делителей у него нет.
«Оканчивается на 30» — это условие на две последние цифры значения , то есть m % 100 == 30. Перебираем числа, начиная с 860001, по возрастанию, пока не найдём пять подходящих.
def M(n):
d = 2
while d * d <= n:
if n % d == 0:
return n // d - d # наибольший делитель минус наименьший
d += 1
return 0 # n простое: делителей нет
n = 860000
found = 0
while found < 5:
n += 1
m = M(n)
if m % 100 == 30: # M оканчивается на 30
print(n, m)
found += 1
Программа выводит:
860064 430030 860199 286730 860264 430130 860464 430230 860499 286830Ответ: 860064 430030 860199 286730 860264 430130 860464 430230 860499 286830