HDU 1164(质因子的分解)

亦凉 2022-09-20 11:22 269阅读 0赞

题意：如题。

#include<iostream>
#include<math.h>
using namespace std;
const int maxn=65536;
int plist[7000];
bool flag[maxn];
int i;
void init()
{
    int max=(int)sqrt(maxn*1.0);
    memset(flag,true,sizeof(flag));
    for(i=2;i<=max;i++)
    {
        if(flag[i])
        for(int j=i*i;j<=maxn;j+=i)
            flag[j]=false;      
    }
    int count=0;
    for(i=2;i<=maxn;i++)
        if(flag[i]) 
        {
            plist[count]=i; 
            count++;
        } 
    //cout<<count<<" "<<plist[count-1]<<endl;
}
int main()
{
    int n;
    init();
    //cout<<plist[0]<<endl;
    while(scanf("%d",&n)!=EOF)
    {
        int index=0;
        while(n>=plist[index])
        {
            //cout<<index<<" "<<plist[index]<<" "<<n<<endl;
            if(n%plist[index]==0)
            {   
                n=n/plist[index];
                if(n!=1) printf("%d*",plist[index]);
                else printf("%d\n",plist[index]); 
                //cout<<plist[index]<<" "<<n<<endl; 
            } 
            else
            {
                index++;    
            }                     
        }
        //cout<<plist[index]<<" "<<n<<endl;                              
    }
    return 0;    
}