【PAT（甲级）】1059 Prime Factors

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1​k1​×p2​k2​×⋯×pm​km​.

Input Specification:

Each input file contains one test case which gives a positive integer N in the range of long int.

Output Specification:

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.

Sample Input:

97532468

Sample Output:

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

解题思路：

输出给出的long int数字的质因子。所以我们先要创建一个函数来判断数字是否是素数，然后如果这个long int本身是个很大的素数就输出它本身即可，可以省去查找因子的时间。

循环判断是否为素数的时候只要循环到即可，这样可以节省时间。

因为要输出有几个这样的质数，所以当找到一个可以整除的质数时，要循环整除，直到这个数不能再被整除为止。（即将给出的数一直除以素数直到被除数为素数为止）

易错点：

1. 对于0，1这样的数字直接输出它本身等于它本身就行，而对于7，11，13也是直接输出；

2. ^前面的是可以整除的素数，后面的是这个素数能被整除的次数（应该就我看题目不仔细了吧O。o？）；

代码：

#include
using namespace std;
 
bool isPrime(long int a){//判断是否为素数
	if(a<2) return 0;
	if(a==2) return 1;
	for(long int i=2;i<=sqrt(a);i++){
		if(a%i==0) return 0;
	}
	return 1;
}
 
int main(){
	long int N;
	scanf("%ld",&N);
	long int k = N;
	int times = 0;
	int first = 1;
	if(N<=1){
		printf("%d=%d",N,N);
		return 0;
	}
	printf("%ld=",N);
	for(long int i=2;i<=k;i++){//将这个数一直除以素数直到被除数为素数为止
		times = 0;
		if(isPrime(i)){
			while(k%i==0){
				k=k/i;
				times++;
			}
			if(times==0){
				continue;
			}
			if(first){
				first = 0;
			}else{
				printf("*");
			}
			if(times==1) cout<
			else printf("%d^%d",i,times);
		}
	}
	return 0;
}