digsum(n)表示一个数字的所有数位的和，比如digsum(105) = 1 + 0 + 4 = 6
设n = p0 * p2 * p3 *...* pk，pi是素数，可能相同
如果digsum(n) = sum(digsum(pi))且n不是素数，那么n就是一个分解平衡树，现在给定一个m，要求比m大的最小的分解平衡数
比如 4 = 2 * 2， digsum(4) = digsum(2) + digsum(2)，所以4是一个分解平衡树
输入：
单组测试数据
输入整数m(1 <= m <= 10^8)
输出
输出一个整数表示答案
样例输入
3
样例输出
4
def is_prime(num):
if num < 2:
return False
elif num == 2 or num == 3:
return True
else:
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
def prime_factorize(num):
if num < 2:
return 0
if is_prime(num):
return 0
else:
pri_fac_list = []
while 1:
if is_prime(num):
pri_fac_list.append(num)
break
for i in range(2, num // 2 + 1):
if is_prime(i) and num % i == 0:
pri_fac_list.append(i)
num = num // i
break
return pri_fac_list
def digsum(n):
return sum([int(i) for i in list(str(n))])
n = int(input())
while True:
res = prime_factorize(n)
if res:
s = sum([digsum(i) for i in res])
if s == digsum(n):
print(n)
break
n += 1
