Prime Factors

article/2025/9/14 4:08:51

此题需要使用到质因子分解的算法，可以参考以下链接：

https://blog.csdn.net/qq_42410605/article/details/100150140

题目描述：

Given any positive integer N,you are supposed to find all of prime factors,and write them in the format:N=p1^k1*p2^k2*#……*pm^km.

输入格式：

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 = p1^k1*p2^k2*#……*pm^km, where pi`s are prime factors of N in increasing order , and the exponent ki is the number of pi hence when there is only one pi , ki is 1 and must NOT be printed out.

输入样例：

97532468

输出样例：

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

题意:

给出一个int范围的整数，按照从小到大的顺序输出其分解为质因数的乘法算式。

思路:

先把素数表打印出来，然后再进行质因子分解的操作。

注意点:

①题目说的是int范围内的正整数进行质因子分解，因此素数表大概开10^5大小就可以了。

②注意n=1需要特判输出"1=1"，否则不会输出结果。

③初学者学习素数和质因子分解容易犯错的地方：

一是在main函数开头忘记调用Find_Prime0函数；

二是 Find_Prime()函数中把i<maxn误写成i≤maxn；

三是没有处理大于sqrt(n)部分的质因子；

四是在枚举质因子的过程中发生了死循环(死因各异)；

五是没有在循环外定义变量来存储sqrt(n)，而在循环条件中直接计算sqrt(n)，这样当循环中使用n本身进行操作的话会导致答案错误。

④给几组可能会发生错误的数据。

程序代码：

#include<cstdio> 
#include<cmath>
const int maxn = 100010;
bool is_prime(int n){		//判断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;}}
}struct factor{int x,cnt;	//x为质因子，cnt为其个数 
}fac[10]; int main(){Find_Prime();	//请务必写上int n,num=0;	//num为n的不同质因子的个数scanf("%d",&n);if(n==1)printf("1=1");		//特判 1 的情况else{printf("%d=",n);int sqr=(int)sqrt(1.0*n);//n的根号 //枚举根号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) {	//计算出质因子prime[i]的个数 fac[num].cnt++;n/=prime[i];}num++;		//不同质因子个数加 1 }if(n==1)break;	//及时退出循环，节省点时间 }if(n!=1)  {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) {printf("^%d",fac[i].cnt);}}}	return 0; 
}