(PAT 1059) Prime Factors (分解质因子)

向右看齐 2022-03-18 02:48 227阅读 0赞

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1k1×p2k2×⋯×pmkm.

### 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

解题思路:

分解质因子即可

这里1需要特判处理,因为程序不会输出1,所以如果输入的数字为1,那么就输出1=1

#include <iostream>
    #include <algorithm>
    #include <math.h>
    using namespace std;
    const int MAXN = 100010;
    long long primelist[MAXN];
    long long objNum;
    int num;
    int index = 0;
    struct factor {
    	long long x, cnt;
    }facs[MAXN];
    
    bool isprime(long long num) {
    	if (num <= 1) return false;
    	for (long long i = 2; i*i <= num; ++i) {
    		if (num % i == 0) return false;
    	}
    	return true;
    }
    //打表
    void primeTable() {
    	for (int i = 2; i < MAXN; ++i) {
    		if (isprime(i)) {
    			primelist[index++] = i;
    		}
    	}
    }
    void getprimefactors() {
    	num = 0;
    	for (int i = 0; i < index; ++i) {
    		if (objNum % primelist[i] == 0) {
    			facs[num].x = primelist[i];
    			facs[num].cnt = 0;
    			while (objNum % facs[num].x == 0) {
    				facs[num].cnt++;
    				objNum /= facs[num].x;
    			}
    			num++;
    		}
    	}
    	if (objNum != 1) {
    		facs[num].x = objNum;
    		facs[num].cnt = 1;
    		num++;
    	}
    }
    
    int main() {
    	scanf("%lld", &objNum);
    	long long printNum = objNum;
    	primeTable();
    	getprimefactors();
    	if(printNum == 1){  //需要特判处理
    	  printf("1=1");
    	  return 0;
    	}
    	printf("%lld=", printNum);
    	for (int i = 0; i < num; ++i) {
    		if(facs[i].cnt == 1){
    			printf("%lld",facs[i].x);
    		}
    		else {
    			printf("%lld^%lld", facs[i].x, facs[i].cnt);
    		}
    		if (i < num - 1) printf("*");
    	}
    
    	return 0;
    }