1142 Smith Numbers

問題概要

ある数nがSmith Numberであるとは、
nの各桁の和と、nの素因数全ての各桁の和が等しいことをいう。
ただし、nが素数であるときはnはSmith Numberではないとする。

ある数nが与えられたとき、nより大きな最小のSmith Numberを求めよ。
nは最大で8桁の自然数である。

解法

nより大きな、なのでnは探索範囲に含まれないことに注意。

n+1から順番に素因数分解してSmith Numberかどうかを調べる。
mを素因数分解するのは単純に√m以下の素因数で割れるだけ割るだけでおｋ.

TLEが厳しいのかと思ったら別にそんなことはなかった。。。

ソースコード

int main()
{
	int n;
	while(scanf("%d",&n),n){
		n++;
		for(;;n++){
			int sum=0,m=n,s=0;
			for(int k=n;k;k/=10)s+=k%10;
			
			for(int i=2;i*i<=m;i++){
				while(m%i==0){
					m/=i;
					for(int k=i;k;k/=10)sum+=k%10;
				}
			}
			if(m==n)continue;
			if(m>1)for(;m;m/=10)sum+=m%10;
			if(sum==s){
				printf("%d\n",n); break;
			}
		}
	}
	return 0;
}