分解质因子
题目描述：给定一个正整数 n，设 n=p1×p2×…pk，其中 pi 均为质数，对 1≤i<k，pi≤pi+1。可以证明，序列 pi 是唯一的。对每个给定的 n，请你求出 p1,p2,…pk。
#include <bits/stdc++.h>
using namespace std;
int x[50001];
int main()
{
long long n, m;
int t, cnt;
bool flag;
scanf("%d", &t);
while (t--)
{
scanf("%lld", &n);
m = n;
flag = true;
cnt = 0;
for ( int i = 2; 1ll * i * i <= n; i++)
{
while (m % i == 0)
{
if (flag)
{
flag = false;
printf("%d", i);
}
else
{
printf(" %d", i);
}
m /= i;
cnt++;
}
}
if (m != 1)
{
if (flag)
printf("%lld", m);
else
printf(" %lld", m);
}
printf("\n");
}
return 0;
}唯一分解定理：对任意大于 1 的正整数 n，设 n 的质因子分别为 p1,p2,…pk，则 n 一定能分解为上述质因子若干次幂的乘积，即 n=p1^c1 p2^c2…pk^ck。并且这种分解方式是唯一的，也就是不存在另一种分解方式使得对应质因子的指数不同。
引理：对任意大于 1 的正整数 n，n 至多有一个大于 n 的质因子。假设该质因子存在，它在唯一分解式中的指数一定是 1。