唯一分解定理

时间:2021-04-23 05:51:35

任意一个大于1的正整数都能表示成若干个质数的乘积,且表示的方法是唯一的。换句话说,一个数能被唯一地分解成质因数的乘积。因此这个定理又叫做唯一分解定理。

题目描述
假设x是一个正整数,它的值不超过65535(即1< x <= 65535),请编写一个程序,将x分解为若干个素数的乘积。
输入
输入的第一行含一个正整数k (1<=k<=10),表示测试例的个数,后面紧接着k行,每行对应一个测试例,包含一个正整数x。
输出
每个测试例对应一行输出,输出x的素数乘积表示式,式中的素数从小到大排列,两个素数之间用“*”表示乘法
示例输入
2
11
9828
示例输出
11
2*2*3*3*3*7*13



#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <iomanip>

using namespace std;
int main()
{
    int i,a[10000],c,n,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        c=0;
        for(i=2;i<=n;i++)
        {
            while(n%i==0)
            {
                a[c++]=i;
                n/=i;
            }
        }
        for(i=0;i<c;i++)
        {
            printf(i==0?"%d":"*%d",a[i]);
        }
        printf("\n");
    }
    return 0;
}