PAT A1059素因子分解（教学题）

题意

求出n所能分解的素因子。

思路

这个应该是套路题，就是打印素数表，然后利用fac数组，枚举1~sqrt(n)范围内的所有素因子p，判断p是否为n的因子。 还要注意如果在枚举完之后，n仍然＞1，那么必定有一个大于sqrt(n)的素因子（很有可能就是n本身），这部分也需要处理。

#include<cstdio> #include<cmath> using namespace std; const int maxn=100010; struct factor{ int x,cnt; //x为质因子，cnt为质因子的个数 }fac[10]; bool is_prime(int n){ //判断是否为素数 if(n==1) return false; int sqr=(int)sqrt(1.0*n); for(int i=2;i<=sqr;i++){ if(n%i==0) return false; } return true; } int prime[maxn],pNum=0; void Find_Prime(){ //打印素数表 for(int i=1;i<maxn;i++){ if(is_prime(i)==true){ prime[pNum++]=i; //prime[]就是素数表 } } } int main(){ Find_Prime(); //必须先打印出素数表 int n,num=0; //num为n的不同素因子的个数 scanf("%d",&n); if(n==1) printf("1=1"); //特别判定n=1的情况 else { printf("%d=",n); int sqr=(int)sqrt(1.0*n); //枚举＜sqrt(n)的素因子 for(int i=0;i<pNum&&prime[i]<=sqr;i++){ if(n%prime[i]==0){ //prime[i]是n的素因子 fac[num].x=prime[i]; //记录该因子 fac[num].cnt=0; //初始化个数 while(n%prime[i]==0){ //计算出该因子的个数 fac[num].cnt++; n/=prime[i]; } num++; //不同素因子的个数+1 } if(n==1) break; //及时退出循环 } if(n!=1){ //如果无法被根号n以内的素因子除尽 fac[num].x=n; //那么一定有一个大于根号n的素因子 fac[num++].cnt=1; } //按格式输出结果 for(int i=0;i<num;i++){ if(i>0) printf("*"); //第二个素因子开始要用乘号* printf("%d",fac[i].x); //素因子 if(fac[i].cnt>1){ //如果个数＞1，则需要把个数也输出 printf("^%d",fac[i].cnt); } } } return 0; }

注意点：

需要在循环外定义sqr，要是在循环条件中直接计算sqrt(n)会导致答案出错。