Задача 5 из 11

Разность простых делителей

Время 3 с · память 256 МБ

Пусть MM — разность максимального и минимального простых натуральных делителей целого числа, не считая самого числа. Если у числа нет таких делителей, значение MM равно нулю. Каждый простой делитель учитывается один раз; если он единственный, то M=0M = 0.

Напишите программу, которая перебирает целые числа, большие AA, в порядке возрастания и ищет среди них такие, для которых значение MM является простым числом и содержит в своей записи не менее четырёх цифр 1.

Входные данные

Во входных данных содержится одно натуральное число AA (A≤108A \le 10^8). Искомые пять чисел существуют при любом допустимом значении AA.

Выходные данные

Выведите первые пять найденных чисел в порядке возрастания, каждое в отдельной строке: сначала само число, затем соответствующее ему значение MM.

Примеры

Ввод 1
1
Вывод 1
22238 11117
22346 11171
44476 11117
44692 11171
66714 11117
Ввод 2
22238
Вывод 2
22346 11171
44476 11117
44692 11171
66714 11117
67038 11171

Примечание

Например, у числа 60 простые делители 2, 3 и 5, поэтому M=5−2=3M = 5 - 2 = 3. У числа 49 единственный простой делитель 7, поэтому M=0M = 0.

В первом примере 22238=2⋅1111922238 = 2 \cdot 11119 и 22346=2⋅1117322346 = 2 \cdot 11173, где 11119 и 11173 — простые числа. Получаются значения M=11117M = 11117 и M=11171M = 11171; оба простые и содержат по четыре цифры 1. Далее подходят 44476=22⋅1111944476 = 2^2 \cdot 11119, 44692=22⋅1117344692 = 2^2 \cdot 11173 и 66714=2⋅3⋅1111966714 = 2 \cdot 3 \cdot 11119: минимальный и максимальный простые делители дают те же значения MM.

Во втором примере граница равна 22238, поэтому это число в ответ не входит. После следующих четырёх чисел из первого примера добавляется 67038=2⋅3⋅1117367038 = 2 \cdot 3 \cdot 11173, для которого M=11173−2=11171M = 11173 - 2 = 11171.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче