PAT 甲级 刷题日记|A 1059 Prime Factors

单词积累

• prime factor 素因数

题目

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
结尾无空行

思路分析

素数判定，这里采用了素数筛选的方法，需要记录质因数及幂。

值得注意的是对1的判定，1不是素数，但在这里却有样例3考察，有些自相矛盾。

在做题中，还是默认1不是素数，不做输出，样例不过再考虑这些。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = sqrt(1e9) + 1;
vector<int> prime;
bool isPrime[maxn];
vector<int> ans1;
vector<int> ans2;
 

void inital() {
    for (int i = 2; i <maxn; i++) {
        isPrime[i] = true;
    }
    for (int i = 2; i <maxn; i++) {
        if (!isPrime[i]) {
            continue;
        }
        prime.push_back(i);
        for (int j = i * i; j < maxn; j += i) {
            isPrime[j] = false;
        }
    }
    return ;
}

int main() {
    long long int N;
    long long int ori;
    inital();
    cin>>N;
    ori = N;
    for (int i = 0; prime[i] <= N; i++) {
        int mi = 0;
        int flag = 0;
        while (N % prime[i] == 0) {
            flag = 1;
            mi++;
            N /= prime[i];
        }
        if (flag) {
            ans1.push_back(prime[i]);
            ans2.push_back(mi);
        }
        
    }
    if (ori == 1) cout<<"1=1";
    if (!ans1.empty()) {
        cout<<ori<<"="; 
    }
    for (int i = 0; i < ans1.size(); i++) {
        if (i != 0) cout<<"*";
        cout<<ans1[i];
        if (ans2[i] != 1) cout<<"^"<<ans2[i];
    }
}