Задача 4 из 11

Сумма крайних делителей

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

Пусть MM — сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если у числа нет таких делителей, значение MM равно нулю. Если такой делитель один, он является и минимальным, и максимальным. Например, для числа 28 имеем M=2+14=16M = 2 + 14 = 16, а для числа 49 — M=7+7=14M = 7 + 7 = 14.

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

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

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

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

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

Примеры

Ввод 1
800000
Вывод 1
800004 400004
800009 114294
800013 266674
800024 400014
800033 61554
Ввод 2
3
Вывод 2
4 4
24 14
33 14
44 24
49 14

Примечание

В первом примере перебор начинается с 800001. Для пяти найденных чисел суммы минимального и максимального делителей равны: 800004:2+400002=400004800004: 2 + 400002 = 400004; 800009:7+114287=114294800009: 7 + 114287 = 114294; 800013:3+266671=266674800013: 3 + 266671 = 266674; 800024:2+400012=400014800024: 2 + 400012 = 400014; 800033:13+61541=61554800033: 13 + 61541 = 61554. Все суммы оканчиваются на 4; у пропущенных при переборе чисел это условие не выполняется.

Во втором примере первое найденное число — 4: его единственный делитель, отличный от единицы и самого числа, равен 2, поэтому M=2+2=4M = 2 + 2 = 4. У простых чисел таких делителей нет, для них M=0M = 0.

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

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

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