首页 > 代码库 > PAT 2-07 素因子分解(C语言实现)

PAT 2-07 素因子分解(C语言实现)

PAT 2-07 素因子分解(C语言实现)

 
 

PAT 2-07 素因子分解(C语言实现),有需要的朋友可以参考下。


题目说明:

 

给定某个正整数N,求其素因子分解结果,即给出其因式分解表达式 N = p1^k1* p2^k2*…*pm^km

输入格式说明:

输入long int范围内的正整数N。

输出格式说明:

按给定格式输出N的素因式分解表达式,即 N = p1^k1* p2^k2*…*pm^km,其中pi为素因子并要求由小到大输出,指数ki为pi的个数;当ki==1即因子pi只有一个时不输出ki

样例输入与输出:

序号输入输出
1
1024
1024=2^10
2
1323
1323=3^3*7^2
3
97532468
97532468=2^2*11*17*101*1291
4
1
1=1
5
3
3=3
解答说明:

从小到大依次寻找素因子,并对每一个素因子的个数做统计。

源码:

 

#include<stdio.h>#include<math.h>int main(void){	int i,j;	long int m, n;	int count;	int isPrime,flag;	isPrime = 1;	flag = 0;	scanf("%ld",&n);	printf("%ld=",n);	m = sqrt(n);	for(i = 2; i <= m;i++){		if(n%i == 0){			//printf("%d",i);			isPrime = 0;			count = 1;			n = n / i;			while(n%i == 0){				n = n / i;				count++;			}			if(flag)				printf("*");			else				flag = 1;			if(count == 1)				printf("%d",i);			else				printf("%d^%d",i,count);		}	}	if(isPrime)		printf("%d",n);		return 0;}

PAT 2-07 素因子分解(C语言实现)