Prime factorization -- C (GCC) -- PTA

  Given a positive integer  N, Find the prime factorization result , That is, the factorization expression is given  N=p1​k1​⋅p2​k2​⋯pm​km​.

【 Input format 】

Input long int Positive integer in range N

【 Output format 】

Output in the given format N Prime factorization expression of , namely  N=p1^k1*p2^k2*…*pm^km, among pi It is a prime factor and requires small to large output , Index ki by pi The number of ; When ki by 1 That's the factor pi No output when there is only one ki.

【 sample input 】

1323

【 sample output 】

1323=3^3*7^2

Code length limit

16 KB

The time limit

400 ms

Memory limit

64 MB

【 Thinking simulation 】

First step ：  If the prime factor grows from small to large , We can set an initial value n=2, Every time you judge n Prime or not , If not n++, If yes, then judge whether it is N Factor of .

The second step ： take n The value is assigned to i, Let the index initially be k=0, because n Only the external cycle can change ,i accord with N After the factor bar of , Make N/=i, When N=0 When, the external loop terminates , Represents that the expression terminates , Judge i Whether it appears for the first time , The first occurrence will i Assign to new variable i1, The purpose of doing this is i1=i when , Just give it to k++ Represents that the latter factor is the same as the previous factor , Index ++,i1 It's not equal to i when , Represents the emergence of new factors , Output the current expression , At this time k=1, Represents the initial value of the new factor .

#include<stdio.h>
#include<math.h>
int main(){
	long int N,n=2,i=0,i1=0,j=2;//i Is a prime factor ,,i1 Is the coefficient ,k Is the index  
	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;
}