PAT-ADVANCED1059——Prime Factors
我的PAT-ADVANCED代码仓:https://github.com/617076674/PAT-ADVANCED
原题链接:https://pintia.cn/problem-sets/994805342720868352/problems/994805415005503488
题目描述:
题目翻译:
1059 质因子
任给一个正整数N,你需要找出它的所有质因子,以下述形式输出它们:N = p1 ^ k1 × p2 ^ k2 × ⋯ × pm ^ km。
输入格式:
每个输入文件包含一个测试用例。每个测试用例包含一个正整数N,其不超过long int的范围。
输出格式:
以N = p1 ^ k1 × p2 ^ k2 × ⋯ × pm ^ km的形式输出结果,其中pi是N的质因子,以増序排列,ki是pi对应的个数,如果ki为1,则不需要打印ki。
输入样例:
97532468
输出样例:
97532468=2^2*11*17*101*1291
知识点:质因子分解
思路:对一个正整数num来说,如果它存在[2, num]范围内的质因子,要么这些质因子全部小于等于sqrt(num),要么只存在一个大于sqrt(num)的质因子,而其余质因子全部小于等于sqrt(num)
(1)枚举1 ~ sqrt(num)范围内的所有质数p,判断p是否是n的因子。
(2)如果在上面步骤后num仍然大于1,说明n有且仅有一个大于sqrt(num)的质因子(有可能是num本身),这时需要增加这个质因子。
注意点:当num == 1或num是质数时,直接输出其本身的值并return 0即可。
时间复杂度和空间复杂度的分析对本题来说意义不大。
C++代码:
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
using namespace std;
struct factor{
int num;
int count;
factor(int _num, int _count) : num(_num), count(_count) {};
};
bool isPrime(int num);
int main(){
vector<factor> primes;
int num;
scanf("%d", &num);
printf("%d=", num);
if(isPrime(num) || num == 1){
printf("%d", num);
return 0;
}
for(int i = 2; i <= sqrt(num); i++){
if(isPrime(i) && num % i == 0){
primes.push_back(factor(i, 0));
}
}
for(int i = 0; i < primes.size(); i++){
while(num % primes[i].num == 0){
primes[i].count++;
num /= primes[i].num;
}
}
if(num != 1){ //如果上述步骤后num仍然大于1,说明num有且仅有一个大于sqrt(num)的质因子(有可能是num本身)
primes.push_back(factor(num, 1));
}
for(int i = 0; i < primes.size(); i++){
if(primes[i].count == 1){
printf("%d", primes[i].num);
}else{
printf("%d^%d", primes[i].num, primes[i].count);
}
if(i != primes.size() - 1){
printf("*");
}
}
return 0;
}
bool isPrime(int num){
if(num == 1){
return false;
}
for(int i = 2; i <= sqrt(num); i++){
if(num % i == 0){
return false;
}
}
return true;
}
C++解题报告: