я особо не вижу, чо тут оптимизировать можно конечно по размеру входного числа сначала примерно подумать куда прыгать, но тут ещё вопрос насколько это поможет. лучше всё-таки полный перебор.
а ещё сама реализация решения очень странная, я бы использовал for