解题思路

素数生成：使用埃拉托斯特尼筛法生成一定范围内的素数。 幂运算：使用快速幂算法计算幂运算结果。 素因数分解：对最终结果进行素因数分解，并输出分解后的结果。

代码分析

素数生成： 使用埃拉托斯特尼筛法生成素数表 is_prime 和素数数组 prime。 素数表 is_prime 用于标记某个数是否为素数。 素数数组 prime 存储所有素数。 幂运算： 使用快速幂算法 pow 计算 x^y，避免溢出。 素因数分解： 将所有幂运算结果相乘后减去 1，得到最终结果。 对最终结果进行素因数分解，记录每个素因数的指数。 输出结果： 按照要求格式输出素因数分解的结果。

原理

埃拉托斯特尼筛法：用于高效生成一定范围内的素数。 快速幂算法：用于高效计算幂运算结果，避免溢出。 素因数分解：通过不断除以素数，分解出每个素因数的指数。

实现步骤

素数生成： 初始化素数表 is_prime，标记所有数为素数。 使用筛法标记合数，生成素数数组 prime。 幂运算： 使用快速幂算法计算每个幂运算结果。 素因数分解： 将所有幂运算结果相乘后减去 1，得到最终结果。 使用素数数组对最终结果进行素因数分解，记录每个素因数的指数。 输出结果： 按照要求格式输出素因数分解的结果。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 33000;
bool is_prime[MAX];
int prime[MAX];

int pow(int x,int n)
{
	int res = 1;
	while (n > 0)
	{
		if (n & 1)
		{
			res *= x;
		}
		x *= x;
		n >>= 1;
	}
	return res;
}

int main()
{
	int x,y,maxx,sum = 1,p = 0;
	int cnt[MAX];
	char ch;
	memset(is_prime,true,sizeof(is_prime));
	memset(prime,0,sizeof(prime));
	is_prime[0] = is_prime[1] = false;
	for (int i = 2;i <= MAX;i++)
	{
		if (is_prime[i])
		{
			prime[p++] = i;
			for (int j = 2 * i;j <= MAX;j += i)
			{
				is_prime[j] = false;
			}
		}
	} 
	while (1)
	{
		scanf("%d",&x);
		if (x == 0)
			break;
		scanf("%d",&y); 
		sum *= pow(x,y); 
		ch = getchar();
		if (ch == '\n')
		{
			maxx = 0;
			memset(cnt,0,sizeof(cnt));
			sum -= 1;
			int tmpsum = sum;
			for (int i = 0;i < tmpsum;i++)
			{
				while (sum % prime[i] == 0)
				{
					cnt[i]++;
					sum /= prime[i];
					maxx = max(maxx,i);
					//cout << sum << endl;
				}
				if (sum == 0 || sum == 1)
					break;
			}
			//cout << "OK" << endl;
			bool first = true;
			for (int i = maxx;i >= 0;i--)
			{
				if (cnt[i])
				{
					first?printf("%d %d",prime[i],cnt[i]):printf(" %d %d",prime[i],cnt[i]);
					first = false;
				}
			}
			printf("\n");
			sum = 1;
		}
	}
	return 0;
}