2013
11-09

# Smith Numbers

While skimming his phone directory in 1982, Albert Wilansky, a mathematician of Lehigh University,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 was so amazed by his discovery that he named this kind of numbers after his brother-in-law: Smith numbers.

As this observation is also true for every prime number, Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number, so he excluded them from the definition.

Wilansky published an article about Smith numbers in the Two Year College Mathematics Journal and was able to present a whole collection of different Smith numbers: For example, 9985 is a Smith number and so is 6036. However,Wilansky was not able to find a Smith number that was larger than the telephone number of his brother-in-law. It is your task to find Smith numbers that are larger than 4937775!

The input file consists of a sequence of positive integers, one integer per line. Each integer will have at most 8 digits. The input is terminated by a line containing the number 0.

For every number n > 0 in the input, you are to compute the smallest Smith number which is larger than n,and print it on a line by itself. You can assume that such a number exists.

4937774
0

4937775

import java.util.Scanner;
public class Main {
public static int sum = 0;
public static boolean isPrime(int num) {
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0)
return false;
}
return true;
}
public static boolean isSmithNumbers(int num) {
String s = String.valueOf(num);
int tempSum = 0;
int k = num;
while (true) {
if (k / 10 > 0) {
tempSum += k % 10;
k /= 10;
} else {
tempSum += k;
break;
}
}
int n = (int)Math.sqrt(num);
for (int i = 2; i <= (int)Math.sqrt(num) ; ) {
if (num % i == 0) {
getSum(i);
num = num / i;
}else
i++;
}
getSum(num);
if (sum == tempSum)
return true;
return false;
}
public static void getSum(int i) {
while (true) {
if (i / 10 > 0) {
sum += i % 10;
i /= 10;
} else {
sum += i;
break;
}
}
}
public static void get(int n) {
while (true) {
sum = 0;
n++;
if (!isPrime(n)) {
if (isSmithNumbers(n)) {
System.out.println(n);
return;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while (n != 0) {
//long b = System.currentTimeMillis();
get(n);
// System.out.println(System.currentTimeMillis() - b);
n = sc.nextInt();
}
}
}

1. 题本身没错，但是HDOJ放题目的时候，前面有个题目解释了什么是XXX定律。
这里直接放了这个题目，肯定没几个人明白是干啥

2. 可以参考算法导论中的时间戳。就是结束访问时间，最后结束的顶点肯定是入度为0的顶点，因为DFS要回溯