Жадные алгоритмы

Для начала отметим, что жадность здесь не работает! Казалось бы, мы хотим, чтобы число содержало как можно меньше разрядов. Поэтому надо начать с 777, но тогда остается сумма 4, которую нельзя представить одной цифрой, являющейся простым числом. Поэтому будем решать задачу по-другому.

Сначала докажем, что в числе не может быть 4 или менее знаков. Трёх точно не хватит, так как максимальная сумма цифр . Далее рассмотрим четырёхзначные числа. Так как 25 — нечётное число, то 4 цифры не могут быть нечётными. Поэтому как минимум одна цифра равна 2, и тогда сумма оставшихся равна 23, и тремя цифрами, не превосходящими 7, её не получить.

Итак, в числе как минимум 5 знаков. Заметим, что 22777 подходит. При этом числа с одинаковым количеством разрядов мы сравниваем по цифрам слева направо, и цифра 2 — минимально возможная. Поэтому все числа, начинающиеся не на 22, будут больше нашего примера. Оставшиеся цифры равны по 7, так как сумму 21 можно получить только с помощью трёх семёрок.