分解素因子(数论)

Description

假设x是一个正整数，它的值不超过65535( 1< x <=65535 )，请编写一个程序，将x分解为若干个素数的乘积。

Input

输入的第一行含一个正整数k (1 <= k <= 65535 )，表示测试例的个数，后面紧接着k行，每行对应一个测试例，包含一个正整数x。

Output

每个测试例对应一行输出，输出x的素数乘积表示式，式中的素数从小到大排列，两个素数之间用“*”表示乘法。

Sample Input

2        11 9828

Sample Output

11       2*2*3*3*3*7*13

解：

#include
       
        using namespace std;#define  M 10000int ans[M],p[M];bool isprime(int n)//判断是否为素数{    if(n<=1)return false;    for(int i=2;i*i<=n;i++)     if(n%i==0)return false;     return true;    }int main(){    int i,n,s=0;    for(i=2;i<=65535;i++)    {        if(isprime(i))        p[s++]=i; //将65535之内的素数全部存入数组p中    }        int t;    //freopen("d:\\1.txt","r",stdin);    cin>>t;    while(t--)    {        int k=0;        cin>>n;        for(i=0;p[i]*p[i]<=n;i++)//求其质因数        {            if(n%p[i]==0)            {                n=n/p[i];                ans[k++]=p[i];                while(n%p[i]==0)                {                    n=n/p[i];                    ans[k++]=p[i];                        }            }            if(n==1)break;        }        if(n>1)        ans[k++]=n;                for(i=0;i