[UVa]10042:Smith Numbers

建質數表硬爆，
把每個數字質因數分解然後再看看加起來有沒有相等這樣。
還有要去掉本身是質數的數字，
因為本身為質數的數字並不能是答案(題目有說)。

[C](0.096)

	#include<stdio.h>
	#include<math.h>
	#define ERROR 0.00000001
	int main()
	{
	int prime[100005] = { 1, 1, 0 };
	int i, j;
	for( i = 2 ; i <= 100000 ; i++ )
	if( !prime[i] )
	for( j = i+i ; j <= 100000 ; j+=i )
	prime[j] = 1;
	int testcase;
	while( scanf( "%d", &testcase ) != EOF )
	{
	for( i = 1 ; i <= testcase ; i++ )
	{
	int n;
	scanf( "%d", &n );
	for( j = n+1 ; ; j++ )
	{
	int sum_left = 0, sum_right = 0;
	int temp = j;
	int sqrt_temp = (int)( sqrt((double)temp) + ERROR );
	int k;
	while( temp )
	{
	sum_left += temp % 10;
	temp /= 10;
	}
	temp = j;
	for( k = 2 ; k <= sqrt_temp ; k++ )
	{
	if( !prime[k] )
	{
	while( !( temp % k ) )
	{
	temp /= k;
	int k_temp = k;
	while( k_temp )
	{
	sum_right += k_temp % 10;
	k_temp /= 10;
	}
	}
	}
	}
	if( temp > 1 )
	{
	if( temp == j )
	continue;
	while( temp )
	{
	sum_right += temp % 10;
	temp /= 10;
	}
	}
	if( sum_left == sum_right )
	{
	printf( "%d\n", j );
	break;
	}
	}
	}
	}
	return 0;
	}

view raw UVa10042.c hosted with ❤ by GitHub