UVa 583 Prime Factors

解題策略

這題要做質因數分解，只要先用篩法建好質數表，接下來就簡單了。
要注意的是這題的數字非常大，很接近 int 的上限，一個不小心就會溢位，要小心。

	/**
	* UVa 583 Prime Factors
	* Author: chchwy
	* Last Modified: 2011.07.21
	*/
	#include<cstdio>
	#include<bitset>
	#include<vector>
	using namespace std;
	enum {MAX = 46340 + 1}; // sqrt(INT_MAX)
	vector<int> prime; //½è¼Æªí
	void sieve()
	{
	bitset<MAX> p;
	p.flip();
	p[0] = p[1] = 1;
	for (int i = 3; i * i < MAX; i += 2)
	{
	if ( p[i] )
	for (int j = i * i; j < MAX; j += i)
	p[j] = 0;
	}
	for (int i = 2; i < MAX; ++i)
	if ( p[i] )
	prime.push_back(i);
	printf("%d\n", prime.back());
	}
	void print_prime_based_representation(int num)
	{
	//special case
	if ( num == 1 || num == -1 )
	{
	printf(" %d\n", num);
	return;
	}
	if (num < 0)
	{
	num = -num;
	printf(" -1 x");
	}
	bool first = true;
	// ¶}©l°µ¦]¦¡¤À¸Ñ
	for (int i = 0; i < prime.size(); ++i)
	{
	if ( prime[i]*prime[i] > num ) break;
	while ( num % prime[i] == 0 )
	{
	num = num / prime[i];
	(first) ? printf(" ") : printf(" x ");
	first = false;
	printf("%d", prime[i]);
	}
	}
	if ( num != 1 )
	{
	(first) ? printf(" ") : printf(" x ");
	printf("%d", num);
	}
	putchar('\n');
	}
	// 49999
	// 99998
	// 20685
	int main()
	{
	sieve();
	int num;
	while (scanf("%d", &num) == 1)
	{
	if (num == 0) break;
	printf("%d =", num);
	print_prime_based_representation( num );
	}
	return 0;
	}

view raw 583.cpp hosted with ❤ by GitHub