Задача 10 из 11

Два простых множителя

Демоверсия 2027Время 4 с · память 256 МБ

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

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

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

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

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

Примеры

Ввод 1
26568
Вывод 1
26569 163
27221 163
27889 167
189569 163
194221 167
Ввод 2
27889
Вывод 2
189569 163
194221 167
260963 163
261941 163
262267 163

Примечание

В первом примере первое найденное число — 26569=163226569 = 163^2. Далее идут 27221=163⋅16727221 = 163 \cdot 167, 27889=167227889 = 167^2, 189569=163⋅1163189569 = 163 \cdot 1163 и 194221=167⋅1163194221 = 167 \cdot 1163. В записи каждого из множителей 16 встречается ровно один раз. Во втором примере граница равна найденному числу 27889: само оно в ответ не входит.

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

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

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