25. Обработка целочисленной информации: Напишите программу, которая перебирает целые числа, большие…
Напишите программу, которая перебирает целые числа, большие $500,000$, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на цифру $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 = 500001
k = 0
while k < 5:
d = f(n)
if d != 0:
print(n, d)
k += 1
n += 1
Функция f(n) находит минимальный натуральный делитель числа $n$, который оканчивается на цифру $9$, но не равен $9$ и самому числу.
Если подходящих делителей нет, функция возвращает $0$.
Программа выведет:
| Число | Минимальный делитель |
|---|---|
| $500002$ | $89$ |
| $500003$ | $71429$ |
| $500004$ | $19$ |
| $500007$ | $166669$ |
| $500013$ | $18519$ |