【PAT甲级 - C++题解】1059 Prime Factors

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

题意

给定一个整数 N NN ，找出它的所有质因子，并按如下格式输出：

N=p1k1×p2k2×...×pmkm

注意： 如果 N = 1 N=1N=1 则输出 1=1。

思路

我们可以直接从 2 22 往后遍历所有质数，然后计算是否是 n nn 的质因子。因为遍历是从小到大进行的，所以可以从 2 22 遍历到 n nn ，尽管遍历的不是质数，由于前面小的质数已经计算完，所以后面大的不是质数的数 n nn 一定不会整除它。

但是由于给定的数据范围比较大，直接遍历到 n nn 可能会超时，所以可以只遍历其所有约数，效果也是一样的，即从 2 22 遍历到 n \sqrt{n} n  。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    printf("%d=", n);
    if (n == 1)    puts("1");
    else
    {
        bool first = true;
        //遍历质数
        for (int i = 2; i <= n / i; i++)
            if (n % i == 0)  //判断是否能除尽
            {
                //计算能除尽该质因子的几次幂
                int k = 0;
                while (n % i == 0)   n /= i, k++;
                if (!first)  cout << "*";
                else    first = false;
                cout << i;
                if (k > 1) cout << "^" << k;
            }
        //如果n已经除不尽且大于1，也要输出到后面
        if (n > 1)
        {
            if (!first)  cout << "*";
            cout << n;
        }
    }
    return 0;
}