欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAT1059 Prime Factors

程序员文章站 2022-07-15 14:00:47
...

传送门:https://pintia.cn/problem-sets/994805342720868352/problems/994805415005503488

思路:筛素数+因式分解模板,很重要

注意n=1的情况

#include <iostream>
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define sca(x) scanf("%d",&x)
#define sca2(x,y) scanf("%d%d",&x,&y)
#define scl(x) scanf("%lld",&x)
#define scs(x) scanf("%s",x)
#define pri(x) printf("%d\n",x)
#define pri2(x,y) printf("%d %d\n",x,y)
#define prs(x) printf("%s\n",(x))
#define prl(x) printf("%lld\n",x)
#define ll long long
#define PII pair<int,int>
#define eps 1e-6
#define inf 1e17
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e5+5;
int vis[maxn];
int prime[maxn];
int cnt=0;
void gao(){
    for(int i=2;i<maxn;i++){
        if(vis[i]) continue;
        prime[cnt++]=i;
        for(int j=2*i;j<maxn;j+=i){
            vis[j]=1;
        }
    }
}
struct node{
    int x,cnt;
}fac[105];
int main() {
   gao();
   int n;
   int tot=0;
   sca(n);
   printf("%d=",n);
   if(n==1){printf("1");return 0;}
   for(int i=0;i<cnt;i++){
     if(n%prime[i]==0){
        fac[tot].x=prime[i];
        fac[tot].cnt=0;
        while(n%prime[i]==0){
            fac[tot].cnt++;
            n/=prime[i];
        }
        tot++;
     }
     if(n==1)break;
   }
   if(n!=1){
    fac[tot].x=n;
    fac[tot++].cnt=1;
   }

   for(int i=0;i<tot;i++){
    if(i>0)printf("*");
    printf("%d",fac[i].x);
    if(fac[i].cnt>1) printf("^%d",fac[i].cnt);
   }
}

 

相关标签: PTA