素因子分解--C（gcc）--PTA

 给定某个正整数 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。

【输入样例】

1323

【输出样例】

1323=3^3*7^2

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

【思路模拟】

第一步： 素因子从小到大的话，我们可以设置一个初始值n=2，每次判断n是否为素数，如果不是就n++，是的话再判断是否为N的因子。

第二步：将n的值赋给i，设指数初始为k=0，因为n只有外部大循环才能改变，i符合N的因子条后，令N/=i，当N=0时即外部循环终止，代表表达式终止，判断i是否第一次出现，第一次出现的话将i赋值给新变量i1，这样做的目的当i1=i时，就给k++代表后一个因子与前一个因子相同，指数++，i1不等于i时，代表出现了新的因子，输出当前表达式，此时令k=1，代表新因子的初始值。

#include<stdio.h>
#include<math.h>
int main(){
	long int N,n=2,i=0,i1=0,j=2;//i为素因子，,i1为系数,k为指数 
	int k=0;
	scanf("%ld",&N);
	printf("%ld=",N);
	if(N==1){
		printf("1");
		return 0;
	}
	while(N!=1){
		i=n;
		for(j=2;j<=sqrt(i);j++){
			if(i%j==0){
				break;
			}
		}
		if(j<=sqrt(i)){
			n++;
			continue;
		}
		if(N%i==0){
			N/=i;
			if(k==0){
				i1=i;
			}
			if(i==i1){
				k++;
			}else{
				if(k==1){
					printf("%ld*",i1);
				}else{
					printf("%ld^%d*",i1,k);
				}
					k=1;
			}
			i1=i;
		}else{
			n++;
		}
		if(N==1){
			if(k==1){
					printf("%ld",i);
				}else{
					printf("%ld^%d",i,k);
				}
		}
	}
	return 0;
}