PAT甲级1059.

目录

A1059

题目

样例

输入:

97532468

输出:

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

思路和坑点

　　首先需要获得素数表，使用筛选法获取素数表，考虑题目给的数值范围，素数表的大小10000即可。然后对每一个素数用除法进行因式分解，直到无法整除为止，由此获得因子的个数。每获得一个因子的信息，遍输出一次。为了控制*号，使用标记进行控制，出了第一个不输出*号以外，其他都需要输出。
　　坑点
　　要注意第三个测试点的特判 1=1

AC代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 10000
bool Prime[MAXN];
void getprime(){                            // 筛选法获得素数表 
    fill(Prime,Prime+MAXN,true);
    Prime[0]=Prime[1]=false;
    for(int i=2;i<MAXN;i++){
        if(Prime[i]){
            for(int j=i+i;j<MAXN;j+=i)
                Prime[j]=false;
        }
    }
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    getprime();
    int n,tag=0;                            //tag为控制*号的标记 
    cin>>n;
    if(n==1) {printf("1=1"); return 0;}     //特判1的情况 （坑点所在，第三个测试点） 
    printf("%d=",n);                        //打印算式的头部 
    for(int i=2;;i++){                      //因数从2开始 
        int cnt=0;                          //用于因数的计数 
        if(Prime[i]){                       //如果该因数是素数 
            while(n%i==0){                  //每次除以因数（直到不能整除），进行分解计数 
                n/=i;    cnt++;
            }
        }
        if(cnt){                            //如果有因数 
            if(tag) putchar('*');           //如果是第一次打印，不需要* 
            tag=1;                          //修改标记 
            if(cnt==1)    printf("%d",i);   //如果因数个数为1，不打印个数 
            else         printf("%d^%d",i,cnt);
        }
        if(n==1)    break;                  //当n分解完成时结束循环 
    }
    return 0;
}