Найти три первых числа Смита, больших заданного числа

task151.py

'''https://t.me/unilecs
Задача 151. Найти три первых числа Смита, больших заданного числа

Число Смита - это составное число, у которого сумма составляющих его цифр равна сумме цифр, составляющих его разложение на простые сомножители.
Например:
    4937775 = 3 * 5 * 5 * 65837,
    4 + 9 + 3 + 7 + 7 + 7 + 5 = 42,
    3 + 5 + 5 + 6 + 5 + 8 + 3 + 7 = 42.
Поэтому топорный подход "в лоб". Проверяем каждое число, большее заданного.
Раскладываем его на простые сомножители, находим суммы цифр, сравниваем.
Оптимизации для слабаков.
'''

from time import time


def prime_factors(n):
    factors = []
    factor = 2
    while factor * factor <= n and n > 1:
        while n % factor == 0:
            factors.append(factor)
            n //= factor
        factor += 1
    if n > 1:
        factors.append(n)
    return factors


def sum_of_digits(n):
    # return sum(map(int, str(n)))
    s = 0
    while n:
        n, r = divmod(n, 10)
        s += r
    return s


def task151(smith_number):
    smiths = []
    while len(smiths) < 3:
        smith_number += 1
        
        factors = prime_factors(smith_number)                
        if len(factors) < 2:
            continue
        
        own_sum = sum_of_digits(smith_number)
        factors_sum = sum(map(sum_of_digits, factors))        
        if own_sum == factors_sum:
            smiths.append(smith_number)

    return smiths


t = time()
print(task151(4937775))                       # [4937818, 4937824, 4937859]
print('{:.6f} sec'.format(time() - t))