《算法笔记》第4章 入门篇（2）---算法初步5.5 质因子分解

1.什么是质因子：

质因子结构：

struct factor { int x,cnt; //x为质因子，cnt为其个数 }fac[10]; //对一个int类型的数字而言，将长度开到10即可

进行质因子分解：

1.如果p是质因子，如下：

if(n%prime[i]==0) //如果prime[i]是质因子 { fac[num].x=prime[i]; //记录该因子 fac[num].cnt=0; while(n%prime[i]==0) //统计出相同质因子个数 { fac[num].cnt++; n/=prime[i]; } num++; //统计不同质因子个数 }

2.如果p不是质因子，如下：

if(n!=1) { fac[num].x=n; //如果到最后n的值不是1，而是别的数，那么把这个数作为最后一个质因子，放到结构中 fac[num++].cnt=1; //那当然把这个数字个数设置为1 }

---

pat A1059

题意：

输入：

1.输入n表示一个int类型的整数

输出：

输出他的质数因子乘积

解题思路：

参考代码：

#include<iostream> #include<math.h> using namespace std; const int maxn=100010; /* 解题思路： 1.判断素数函数is_prime()，求素数表函数Find_Prime(),设置质因子结构factor 2.如果输入1，则输出1=1 3.主函数结构如下： 1.先构造素数表 2.如果为1则输出1=1 3.否则的话，一句说完：从素数表中进行查找，然后n能整除在先再结构中保留这个数，然后在利用while循环，统计这个素数的个数，就这样不断的走素数表，直到最后n除完为1 4.输出的话还是有点像每个数之间输出一个空格，然后在末尾没有空格，只不过这里是输出*，如果对于该素数的个数大于1的话，则输出^+个数 */ bool is_prime(int n) //判断n是否为素数 { if(n<=1) return false; for(int i=2; i*i<=n; 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; } } } struct factor { int x,cnt; //x为质因子，cnt为其个数 }fac[10]; int main() { Find_Prime(); //先求素数表 int n,num=0; //num为n的不同质因子个数 cin >> n; if(n==1) //如果输入1，则就输出1=1 cout << "1=1"; else { cout << n << "="; //n在这里输出的目的是：后面会改变n的值，所以提前输出 int sqr=(int)sqrt(1.0*n); //n的根号 //枚举根号n以内的质因子 for(int i=0; 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) //计算出质因子prime[i]的个数 { fac[num].cnt++; n/=prime[i]; } num++; //不同质因子个数加1 } if(n==1) //关键在于这里，如果到最后一个素数，那么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) cout << "*"; cout << fac[i].x; if(fac[i].cnt>1) printf("^%d",fac[i].cnt); } } return 0; }

呃呃

---