UVa 516 Prime Land

這題是考質因數分解，先把質因數分解表示法轉成數字，數字減一後，再轉回質因數分解表示法。

Input:
18 1 17 1 15 1 
17 1 11 1 
11 1 29 1 9 1 
2 1 4 1 5 1 7 1 11 1 
18 1 23 1 29 1 
31 1 29 1 
2 3 11 2 25 1 
41 2 
51 1 5 1 
17 1 19 1 23 1 
0

Output: 
353 1 13 1 
31 1 3 1 2 1 
41 1 7 1 5 1 2 1 
3079 1 
7 4 5 1 
449 1 2 1 
3457 1 7 1 
7 1 5 1 3 1 2 4 
127 1 2 1 
619 1 3 1 2 2

最近狂殺質數題。

	/**
	* UVa 516 Prime Land
	* Author: chchwy
	* Last Modified: 2011.07.20
	*/
	#include<iostream>
	#include<sstream>
	#include<vector>
	#include<cstdio>
	#include<cmath>
	#include<cstring>
	using namespace std;

	enum { MAX = 32767 + 1 };

	vector<int> prime;

	// 用埃式篩法建質數表
	int sieve()
	{
	char map[MAX];
	memset(map, 1, sizeof(map));

	map[0] = map[1] = 0;

	for (int i = 2; i < MAX; ++i)
	{
	if ( map[i] )
	for (int j = i * i; j < MAX; j += i )
	map[j] = 0;
	}

	for (int i = 0; i < MAX; ++i)
	if ( map[i] == 1 )
	prime.push_back(i);
	}

	// 把質因數分解表示法轉成整數值
	int to_int_value( string& line )
	{
	int result = 1;

	istringstream sin(line);

	int base, exp;
	while ( sin >> base >> exp )
	{
	for (int i = 0; i < exp; ++i)
	result = result * base;
	}
	return result;
	}

	bool is_prime( int n )
	{
	for (int i = 0; prime[i]*prime[i] <= n; ++i)
	if ( n % prime[i] == 0 )
	return false;
	return true;
	}

	// 把整數轉回質因數表示法
	void to_prime_base_string(int num)
	{
	if ( is_prime(num) ) // special case
	{
	printf("%d 1\n", num);
	return;
	}

	bool first = true;

	for (int i = prime.size() - 1; i >= 0; --i)
	{
	int factor_exp = 0;

	while (num % prime[i] == 0)
	{
	num = num / prime[i];
	factor_exp++;
	}

	if ( factor_exp == 0 ) continue;

	if ( !first )
	printf(" ");
	first = false;

	printf("%d %d", prime[i], factor_exp);
	}
	printf("\n");
	}

	int main()
	{
	#ifndef ONLINE_JUDGE
	freopen("516.in", "r", stdin);
	#endif
	sieve();

	string line;
	while (getline(cin, line))
	{
	if (line == "0") break;

	int num = to_int_value(line);
	num = num - 1;
	to_prime_base_string(num);
	}
	return 0;
	}

view raw 516.cpp hosted with ❤ by GitHub

調和的靈感