[UVa]583:Prime Factors

建質數表去質因數分解即可。

[C](1.708)

	#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 g;
	while( scanf( "%d", &g ) != EOF && g != 0 )
	{
	printf( "%d =", g );
	if( g < 0 )
	{
	printf( " -1 x" );
	g = -g;
	}
	int print = 0;
	int sqrt_g = (int)( sqrt((double)g) + ERROR );
	for( i = 2 ; i <= sqrt_g ; i++ )
	if( !prime[i] )
	while( !(g % i) )
	{
	g /= i;
	if( print )
	printf( " x" );
	print = 1;
	printf( " %d", i );
	}
	if( g > 1 )
	{
	if( print )
	printf( " x" );
	printf( " %d", g );
	}
	printf( "\n" );
	}
	return 0;
	}

view raw UVa583.c hosted with ❤ by GitHub