PAT甲级 1059. Prime Factors

前言

这道题目是25分题,第二道第三道难度,需要有特定的数学知识作为背景。

题目原文

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p​1^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 = p​1^k1*p2^k2*…*pm^km, where pi’s are prime factors of N in increasing order, and the exponent k​i is the number of pi – hence when there is only one p​i, ki is 1 and must NOT be printed out.

Sample Input:
97532468

Sample Output:
97532468=2^2*11*17*101*1291

解题思路

这题的前提是要知道质因数分解定律,而啥也不知道的我虽然一开始完全不知道,但是很快我就意识到这个题目要有结果则必须要有一个条件——所有的给定数一定能由有限个素数相乘得到,所以纯靠暴力算法是行不通的,于是放弃题目上网找资料。

果然,确实存在上述定理。

那么题目就是纯粹的已有算法的重现了,麻烦一点的可能是不能按网上的找到一个因子就输出,而是要先记录下来再按规定的格式输出。我这里用的map记录。

具体的算法是,i从2开始(如果N小于等于2就直接输出),用i除N,如果能整除,就说明i是一个素数因子,然后N /= i循环上述步骤,直到不能整除,就i++,继续。那么如果纯粹+1的操作不会导致出现非素数的因子吗?不会。由于从2开始,如果N里面还有2的倍数,那么肯定能再第一步里整除,无法进入到后面的+1步骤去,所以进入+1了说明之前能整除的i的倍数不会成为N的因子了,比如4,在i加到4之前,就已经分解为2*2了。之后的也类似。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

int main(void) {
// input
long int N;
scanf("%ld", &N);

// handle
printf("%ld=", N);
if(N <= 2) {
printf("%ld", N);
} else {
map<int, int> factors;
for(int i = 2; i <= N; i++) {
while(N % i == 0) {
factors[i]++;
N /= i;
}
}
for(auto iter = factors.begin(); iter != factors.end(); iter++) {
if(iter == factors.begin()) {
if((*iter).second > 1) {
cout << (*iter).first << "^" << (*iter).second;
} else {
cout << (*iter).first;
}
} else {
if((*iter).second > 1) {
cout << "*" << (*iter).first << "^" << (*iter).second;
} else {
cout << "*" << (*iter).first;
}
}
}
if(N != 1) {
cout << "*" << N;
}
}

return 0;
}

后记

这题不会做是真的没办法,完全是相关知识不知道,这里说明,第一,要广泛学习,尤其是算法以及其各种数学理论,尤其是数论相关;第二,像这题如果发现不给定某个规定,比如这里的质因数分解定理,就无法做下去的话,或者变得超乎寻常的复杂时,那就默认这个规定成立从而去做。当然这题如果冷静分析其实也可以通过设计算法得到同样的算法,只是知道背后的数学背景会更快更从容地设计算法。