25. Обработка целочисленной информации: Напишите программу, которая перебирает целые числа, большие…
Напишите программу, которая перебирает целые числа, большие $600,000$, в порядке возрастания и ищет среди них такие, у которых есть натуральный делитель, оканчивающийся на цифру $8$ и не равный ни самому числу, ни числу $8$.
В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – наименьший делитель для каждого из них, оканчивающийся цифрой $8$, не равный ни самому числу, ни числу $8$.
| | |
Для каждого числа найдём все пары делителей. Достаточно перебирать делители до $\sqrt n$: если $d$ является делителем числа $n$, то второй делитель пары равен $\dfrac{n}{d}$.
Среди всех подходящих делителей выбираем минимальный, который оканчивается на цифру $8$ и не равен $8$ и самому числу.
from math import isqrt
def f(n):
a = []
for d in range(1, isqrt(n) + 1):
if n % d == 0:
if d % 10 == 8 and d != 8 and d != n:
a.append(d)
k = n // d
if k % 10 == 8 and k != 8 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$, который оканчивается на цифру $8$, но не равен $8$ и самому числу.
Если подходящих делителей нет, функция возвращает $0$.
Программа выведет:
| Число | Минимальный делитель |
|---|---|
| $600008$ | $358$ |
| $600010$ | $58$ |
| $600012$ | $18$ |
| $600016$ | $300008$ |
| $600020$ | $38$ |