UniLecs #151. Числа Смита

Задача: просматривая свою телефонную книжку в 1982 году, математик Альберт Вилански обратил внимание на то, что телефонный номер его зятя Гарольда Смита (493-7775) обладал интересным свойством: сумма его цифр равнялась сумме цифр всех его простых сомножителей (единица не в счёт).

Число 4 937 775 раскладывается на простые сомножители следующим образом:

4 937 775 = 3 × 5 × 5 × 65 837.

Сумма цифр телефонного номера равна 4 + 9 + 3 + 7 + 7 + 7 + 5 = 42, и сумма цифр его разложения на простые сомножители также равна 3 + 5 + 5 + 6 + 5 + 8 + 3 + 7 = 42. Вилански назвал такой тип чисел по имени своего зятя. Так как этим свойством обладают все простые числа, Вилански не включил их в определение.

Найдите 3 числа Смита, следующие за телефонным номером зятя этого математика.

Входные данные: N - число смита

Вывод: 3 следующих числа Смита после N

Пример: без примеров ☺☺☺.

Идея: принимаем за N исходное число 4937775 и трижды вызываем функцию, которая будет возвращать следующее число Смита после N.

Данная функция организует бесконечный цикл, начиная с N+1 (увеличивая его на 1 на каждом шаге), в котором будет раскладывать число на простые сомножители. И, к примеру, преобразовывать в строку исходное число и все числа простых сомножителей, а затем суммировать каждый символ, преобразовывая его обратно в число.

P.S. Кому не нравится такой подход (уверен, некоторые захотят высказать своё «фи» на этот счёт), можно суммировать цифры, складывая остатки от деления на 10. В любом случае, если кол-во сомножителей больше 1 (т.е. число не является простым) и обе суммы совпадают, цикл прерывается и возвращается текущее значения счётчика цикла.

Ответом для данной задачи являются числа 4937818, 4937824, 4937859.

Реализация:

Метод расчёта с использованием строк

https://gist.github.com/unilecs/a86723c109aabbc9c0663ac5080cb190

Test: https://repl.it/@unilecs/JaggedBrownDisassembly

Метод расчёта через суммы остатков от деления на 10

https://gist.github.com/unilecs/1aa87b59c484ec5dbf04feaaf852d655

Test: https://repl.it/@unilecs/FatalDefenselessRoutes

Еще одно решение на С++:

https://gist.github.com/jin-x/1cb49f7b2e3b530b7cdf57389294a5f9

Test C++: https://repl.it/@jin_x/UniLecs-151-SmithNumberscpp