25. Обработка целочисленной информации: Напишите программу, которая перебирает целые числа, большие…
Напишите программу, которая перебирает целые числа, большие $600,000$, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на цифру $9$ и не равный ни самому числу, ни числу $9$. Вывести первые пять найденных чисел и для каждого минимальный делитель, оканчивающийся на цифру $9$, не равный ни самому числу, ни числу $9$.
Формат вывода: для каждого из пяти таких найденных чисел в отдельной строке сначала выводится само число, затем – значение наименьшего делителя, оканчивающегося на цифру $9$, не равного ни самому числу, ни числу $9$.
Строки выводятся в порядке возрастания найденных чисел.
| | |
Для каждого числа найдём все пары делителей. Достаточно перебирать делители до $\sqrt n$: если $d$ делит число $n$, то второй делитель пары равен $\dfrac{n}{d}$.
Среди всех подходящих делителей выбираем минимальный, который оканчивается на цифру $9$ и не равен $9$ и самому числу.
from math import isqrt
def f(n):
a = []
for d in range(1, isqrt(n) + 1):
if n % d == 0:
if d % 10 == 9 and d != 9 and d != n:
a.append(d)
k = n // d
if k % 10 == 9 and k != 9 and k != n:
a.append(k)
if a:
return min(a)
return 0
n = 600001
k = 0
while k < 5:
d = f(n)
if d != 0:
print(n, d)
k += 1
n += 1
Функция f(n) находит минимальный натуральный делитель числа $n$, который оканчивается на цифру $9$, но не равен $9$ и самому числу.
Если подходящих делителей нет, функция возвращает $0$.
Программа выведет:
| Число | Минимальный делитель |
|---|---|
| $600001$ | $19$ |
| $600003$ | $409$ |
| $600005$ | $49$ |
| $600007$ | $7229$ |
| $600008$ | $179$ |