/****************************************************************
*WA了3次，终于想通了^0^喜欢java的朋友一起来切除啊！
*其实这道题目很简单的！我WA就WA在不知道Smith Number的上界是多少。
*个人认为，该题最有意义的部分就是：把一个数n因式分解时，只需要
*求出不大余sqrt（n）的因子a就可以了，因为一定存在另一个大余sqrt（n）
*的对应因子b，使得n=a*b。
*这样问题的规模就减少到sqrt（n），不是n。

*有一点很郁闷！只能把所有的方法和数据域都声明成static！
*因为要在main这个static方法里调用啊！
***************************************************************/
import java.io.*;
import java.util.*;
class  Main
{
	private static int[] primeArray;
	private static int arraySize;

	public static void main(String[] args) throws Exception
	{
		primeArray=new int[3000];
		arraySize=Seive(primeArray,11000);//WA在这里，
		//不知道Smith Number的上界是多少
		/**************************************************
		*题目中说，最大是8位数，我找出了最大的Smith Number
        100000165（9位数）
		**************************************************/

		BufferedReader cin=new BufferedReader(new
			InputStreamReader(System.in));
		String str;
		StringTokenizer strtoken;
		int start;
		
		str=cin.readLine();
		strtoken=new StringTokenizer(str);
		start=Integer.parseInt(strtoken.nextToken());

		while(start!=0)
		{
			long SmithNumber=getSN((long)start);
			System.out.println(SmithNumber);

			str=cin.readLine();
			strtoken=new StringTokenizer(str);
			start=Integer.parseInt(strtoken.nextToken());

		}
	}

//Get the minimum Smith Number lager than start
private static long getSN(long start)
	{
		long i;
		int  a,b;
		i=start+1;
		while(true){
			a=sumOf(i);
			b=primeSumOf(i);
			if(a==b)break;
			else ++i;
		}
		return i;
	}

//The digits Sum of a long
private static int sumOf(long a)
	{
		int s=0;
		while(a/10>0){
			s+=(int)(a%10);
			a/=10;
		}
		return (s+(int)a);
	}

//The Prime factors' digits sum of a long
private static int primeSumOf(long a)
	{
		int i,j;
		int s=0,num,b;
		long at=a;
		b=(int)Math.sqrt((double)a);
		
		i=0;
		j=primeArray[i];
		while(j<=b&&a!=1){		
				if(a%j==0)
				{	
					num=0;
					while(a%j==0)
					{a/=j;++num;}
					s+=(sumOf(j)*num);
				}
				i++;
				j=primeArray[i];
		}

	 if(at==a)return 0;
	 else if(a==1)return s;
	 else return s+sumOf(a);

	}

//Seive out all the prime numbers less than Integer high
private static int Seive(int[] primeArray,int high)
	{
		BitSet number=new BitSet(high+1);
		int sqrtHigh=(int)Math.sqrt((double)high);
		int i,j;
		for(i=2;i<=sqrtHigh;++i)
			if(!number.get(i))
			{   j=i+i;
				while(j<=high)
				{
					number.set(j);
					j+=i;
				}
			}

		primeArray[0]=2;
		j=1;
		for(i=3;i<=high;++i)
			if(!number.get(i))primeArray[j++]=i;
		
		return j;
	}
}

• 请问你的QQ是多少啊？ (2912) jackjack 2005-04-28 23:58:34
• Re:WA了3次，终于想通了^0^喜欢java的朋友一起来切除啊！ (2912) zsldg2006 2006-09-17 15:28:07
• Re:给几个数据啊，找不出来错啊！！！！ (71) woshiniya 2006-09-21 12:20:06
• Re:WA了3次，终于想通了^0^喜欢java的朋友一起来切除啊！ (85) woshiniya 2006-09-21 12:21:24