题目描述

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​​​​.

输入描述

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

输出描述

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

输入例子

97532468

输出例子

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

我的代码

#include<cstdio>
#include<math.h>
const int maxn=100010;
struct factor{
    int x;
    int cnt;
}fac[10];
int prime[maxn],num=0;  //素数表的个数 

bool isPrime(int a){
    if(a==1) return false;
    int sqr=(int)sqrt(1.0*a);
    for(int i=2;i<=sqr;i++){
        if(a%i==0){
            return false;
        }
    }
    return true;
}

void find_prime(){
    for(int i=1;i<maxn;i++){
        if(isPrime(i)){
            prime[num++]=i;
        }
    }
}


int main(){
    find_prime();
    int n;
    scanf("%d",&n);
    if(n==1){  //如果是1的话直接输出 
        printf("1=1");
        return 0;
    }
    printf("%d=",n);
    int j=(int)sqrt(1.0*n),k=0;
    for(int i=0;i<num&&prime[i]<=j;i++){  //小于sqrt(n) 
        if(n%prime[i]==0){
            fac[k].x=prime[i];  
            fac[k].cnt=0;
            while(n%prime[i]==0){
                fac[k].cnt++;
                n=n/prime[i];
            }
            k++;
        }
        if(n==1) break;
    }
    if(n!=1){
        fac[k].x=n;
        fac[k].cnt=1;
        k++;
    }
    for(int i=0;i<k;i++){
        if(i==0){
            if(fac[i].cnt>1){
                printf("%d^%d",fac[i].x,fac[i].cnt);
            }
            else if(fac[i].cnt==1){
                printf("%d",fac[i].x);
            }
        }
        
        else{
            if(fac[i].cnt>1){
                printf("*%d^%d",fac[i].x,fac[i].cnt);
            }
            else if(fac[i].cnt==1){
                printf("*%d",fac[i].x);
            }
        }
    }
    return 0;
}