首页 > 代码库 > 1059. Prime Factors (25)

1059. Prime Factors (25)

注意n=n这种情况

// 1059.cpp : 定义控制台应用程序的入口点。//#include<iostream>#include<queue>#include<vector>#include<algorithm>using namespace std;queue<long int> prime;vector<pair<long int,long int> > col;void printElem(const pair<int,int> it){    if(it.second==1)    {        printf("%ld*",it.first);    }    else    {        printf("%ld^%ld*",it.first,it.second);    }}int main(){    long int n;    freopen("1059.txt","r",stdin);    while(scanf("%ld",&n)!=EOF)    {        prime.push(2);        for(long int i=3;i<=sqrt(n*1.0);i++)        {            bool flag=true;            for(long int j=2;j<=sqrt(i*1.0);j++)            {                if(i%j==0)                {                    flag=false;                    break;                }            }            if(flag)            {                prime.push(i);            }        }        //cal        long int iter=n;                 while(true)        {            int tmp=prime.front();            prime.pop();            int num=0;            while(iter%tmp==0)            {                iter=iter/tmp;                num++;            }            if(num!=0)                col.push_back(make_pair(tmp,num));            if(prime.empty()||iter==1)                break;        }        if(col.size()==0)        {            printf("%ld=%ld\n",n,n);            continue;        }        printf("%ld=",n);        vector<pair<long int,long int> >::iterator it;        int num=0;        for(it=col.begin();it!=col.end();it++)        {            if(it->second==1)            {                printf("%ld",it->first);            }            else            {                printf("%ld^%ld",it->first,it->second);            }            num++;            if(num!=col.size())                printf("*");            else                printf("\n");        }    }    return 0;}

 

1059. Prime Factors (25)