(PAT 1059) Prime Factors (分解质因子)-蒲公英云

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

向右看齐 2022-03-18 02:48 332阅读 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;
}