[UVa]10392:Factoring Large Numbers

建質數表去質因數分解，注意質數表最高要建到的範圍(題目有寫)。

[C](0.044)

	#include<stdio.h>
	#include<math.h>
	#define ERROR 0.00000001
	int prime[1000005] = { 1, 1, 0 };
	int main()
	{
	long long i, j;
	for( i = 2 ; i <= 1000000 ; i++ )
	if( !prime[i] )
	for( j = i+i ; j <= 1000000 ; j+=i )
	prime[j] = 1;
	long long value;
	while( scanf( "%lld", &value ) != EOF && value >= 0 )
	{
	long long value_temp = (long long)(sqrt( (double)value ) + ERROR);
	if( value_temp > 1000000 )
	value_temp = 1000000;
	for( i = 2 ; i <= value_temp ; i++ )
	{
	if( !prime[i] )
	while( !(value % i) )
	{
	value /= i;
	printf( " %lld\n", i );
	}
	}
	if( value > 1 )
	printf( " %lld\n", value );
	printf( "\n" );
	}
	return 0;
	}

view raw UVa10392.c hosted with ❤ by GitHub