Smith Numbers
时间: 1ms 内存:64M
描述:
Smith Numbers
While skimming his phone directory in 1982, mathematician Albert Wilansky noticed that the telephone number of his brother-in-law H. Smith had the following peculiar property: The sum of the digits of that number was equal to the sum of the digits of the prime factors of that number. Got it? Smith's telephone number was 493-7775. This number can be written as the product of its prime factors in the following way:
4937775 = 3 . 5 . 5 . 65837
The sum of all digits of the telephone number is 4 + 9 + 3 + 7 + 7 + 7 + 5 = 42, and the sum of the digits of its prime factors is equally 3 + 5 + 5 + 6 + 5 + 8 + 3 + 7 = 42. Wilansky named this type of number after his brother-in-law: the Smith numbers.
As this property is true for every prime number, Wilansky excluded them from the definition. Other Smith numbers include 6,036 and 9,985.Wilansky was not able to find a Smith number which was larger than the telephone number of his brother-in-law. Can you help him out?
输入:
The input consists of several test cases, the number of which you are given in the first line of the input. Each test case consists of one line containing a single positive integer smaller than 109.
输出:
For every input value n, compute the smallest Smith number which is larger than n and print it on a single line. You can assume that such a number exists.
示例输入:
1
4937774
示例输出:
4937775
提示:
参考答案:
文章评论