题目:http://pat.zju.edu.cn/contests/pat-a-practise/1059
题解:
要点就是分解质因数。从小到大枚举即可。
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<string> #include<vector> #include<map> #include<set> #include<algorithm> #include<sstream> using namespace std; bool isPrime(int x) { int len=sqrt(x)+1; for(int i=3;i<=len;++i) { if(x%i==0) return false; } return true; } int main() { int n,len; scanf("%d",&n); printf("%d=",n); if(n==1) { printf("1\n"); } else { len=n; for(int i=2,j;i<=len;++i) { j=0; if(isPrime(i)) { for(;n%i==0;) { n/=i; ++j; } } if(j>1) printf("%d^%d",i,j); else if(j==1) printf("%d",i); if(n>1&&j>0) printf("*"); if(n==1) break; } } return 0; }