1059 Prime Factors

发布时间：2020-12-13 23:31:33 所属栏目：Linux 来源：网络整理

导读：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 contai

Given any positive integer?

Input Specification:

Each input file contains one test case which gives a positive integer?

Output Specification:

Factor?

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 0x3f3f3f
using 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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!