首页 > 专题系列 > Java解POJ > POJ 1142 Smith Numbers [解题报告] Java
2013
11-09

POJ 1142 Smith Numbers [解题报告] Java

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要回溯