1059 Prime Factors

概述Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p?1???k?1????×p?2???k?2????×?×p?m???k?m????. Input Specification: Each input file cont

Given any positive integer @H_403_9@N,you are supposed to find all of its prime factors,and write them in the format @H_403_9@N = @H_403_9@p?1???k?1????×p?2???k?2????×?×p?m???k?m????.

input Specification:

Each input file contains one test case which gives a positive integer @H_403_9@N in the range of long int.

Output Specification:

Factor @H_403_9@N in the format @H_403_9@N = @H_403_9@p?1??^@H_403_9@k?1??*@H_403_9@p?2??^@H_403_9@k?2??*…*@H_403_9@p?m??^@H_403_9@k?m??,where @H_403_9@p?i??‘s are prime factors of @H_403_9@N in increasing order,and the exponent @H_403_9@k?i?? is the number of @H_403_9@p?i?? -- hence when there is only one @H_403_9@p?i??, @H_403_9@k?i?? is 1 and must NOT be printed out.

Sample input:

97532468

Sample Output:

97532468=2^2*11*17*101*1291

/*    name:    copyright:    Author:  流照君    Date: 2019/8/6 11:09:58    Description:*/#include <iostream>#include<string>#include <algorithm>#include <vector>#include<cmath>#define inf 0x3f3f3fusing namespace std;typedef long long ll;ll prime[inf],a[inf];ll num=1;voID sIEve(int n){    for(int i=2;i<=n;i++)    {        if(a[i]==0)        prime[num++]=i;        for(int j=i*2;j<=n;j=j+i)        {            a[j]=1;        }    }}int main(int argc,char** argv){    //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    fill(a,a+inf,0);    ll n,flag=0;    cin>>n;    sIEve(500000);    //for(int i=1;i<=num;i++)    //cout<<prime[i]<<" ";    //cout<<endl;    if(n==1)    {        cout<<n<<"="<<"1";        return 0;    }    cout<<n<<"=";    for(int i=1;i<num;i++)    {        int sum=0;        while(n%prime[i]==0)        {            n=n/prime[i];            sum++;        }        if(flag&&sum)        {            if(sum==1)                cout<<"*"<<prime[i];            if(sum>=2)            {                cout<<"*"<<prime[i]<<"^"<<sum;            }            }        if(flag==0&&sum)        {            if(sum==1)                cout<<prime[i];            if(sum>=2)            {                cout<<prime[i]<<"^"<<sum;            }            flag=1;        }        if(n==1)        return 0;    }    return 0;}

别忘了考虑特例 1

总结

以上是内存溢出为你收集整理的1059 Prime Factors全部内容，希望文章能够帮你解决1059 Prime Factors所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。