1059. Prime Factors (25)

雨点打透心脏的1/2处 2021-11-22 04:56 153阅读 0赞

注意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;
    }

转载于:https://www.cnblogs.com/championlai/p/4117103.html