[UVa]382:Perfection

先建質數表，將輸入值給質因數分解，
利用質因數分解的結果求出所有因數之和，
將所有因數之和扣除掉自己本身，再比較大小即是答案。

P.S. 利用質因數分解的結果求出所有因數之和是數學的公式，
是每一個質因數從自己的0次方加到自己在質因數分解中的最高次方，
接著在把求出來所有的和相乘起來即可得解。
Ex. 12: 2^2 * 3^1
12所有因數之和：(2^0+2^1+2^2)*(3^0+3^1) = (1+2+4) * (1+3) = 28
驗證：12之因數：1,2,3,4,6,12
12所有因數之和：1+2+3+4+6+12=28

[C](0.016)

	#include<stdio.h>
	#include<math.h>
	#define ERROR 0.0000001
	int main()
	{
	int prime[60005] = {1,1,0};
	int i, j;
	for( i = 2 ; i <= 60000 ; i++ )
	if( !prime[i] )
	for( j = i+i ; j <= 60000 ; j += i )
	prime[j] = 1;
	int N;
	printf( "PERFECTION OUTPUT\n" );
	while( scanf( "%d", &N ) != EOF && N != 0 )
	{
	int divisor[60005] = {0};
	int temp = N;
	int sqrt_N = (int)( sqrt((double)N) + ERROR );
	for( i = 2 ; i <= sqrt_N ; i++ )
	if( !prime[i] )
	while( temp % i == 0 )
	{
	temp /= i;
	divisor[i]++;
	}
	int product = 1;
	int powsum, singlepow;
	for( i = 2 ; i <= sqrt_N ; i++ )
	if( divisor[i] )
	{
	powsum = 1;
	singlepow = 1;
	for( j = 1 ; j <= divisor[i] ; j++ )
	{
	singlepow *= i;
	powsum += singlepow;
	}
	product *= powsum;
	}
	if( temp != 1 )
	product *= temp+1;
	product -= N;
	printf( "%5d ", N );
	if( product == N )
	printf( "PERFECT\n" );
	else if( product > N )
	printf( "ABUNDANT\n" );
	else
	printf( "DEFICIENT\n" );
	}
	printf( "END OF OUTPUT\n" );
	return 0;
	}

view raw UVa382.c hosted with ❤ by GitHub