PAT A1059 Prime Factors（分解质因数板题）

本文主要是介绍PAT A1059 Prime Factors（分解质因数板题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

给出一个int范围的整数，按照从小到大的顺序输出分解为质因数的乘法公式。

Sample Input:

97532468

Sample Output:

97532468=2^2*11*17*101*1291

Solution

分解质因数板题。注意：

分解int范围正整数，素数表开10,000大小就够了。
n==1时，因为1不是素数需要单独判断。
不要忘记处理>sqrt(n)的一个质因数。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
//数组不需要开到int型最大值那么大
//分解质因数后质因数不会太大
const int maxn = 10000;
bool judge_prime[maxn];
int prime[maxn];
int num_fac, num_prime = 0;
void get_prime()
{// 素数筛法得到素数表memset(judge_prime, true, sizeof(judge_prime));judge_prime[1] = judge_prime[0] = false;for (int i = 2; i < maxn; i++){if (judge_prime[i] == true)for (int j = i + i; j < maxn; j += i)judge_prime[j] = false;}for (int i = 2; i <= maxn; i++){if (judge_prime[i])prime[num_prime++] = i;}
}
struct Factor
{int x, count; //x为质因子，count为其个数初始化为0Factor(){count=0;}
} fac[100];
void prime_factor(int n)
{// n==1时单独处理if (n == 1)fac[num_fac++].x = 1, fac[num_fac].count = 1;else{// 从2到n的开方区间内判断质因数int bound = (int)sqrt(1.0 * n);for (int i = 0; i < num_prime && prime[i] <= bound; i++){if (n % prime[i] == 0){fac[num_fac].x = prime[i];while (n % prime[i] == 0){// 计算同一个质因数出现几次n = n / prime[i];fac[num_fac].count++;}num_fac++;}}// 如果无法被sqrt(n)以内的质因数除尽// 一定有一个>sqrt(n)的质因数if (n != 1){fac[num_fac].x = n;fac[num_fac].count++;num_fac++;}}
}
int main()
{// freopen("in.txt", "r", stdin);get_prime();int n;while (~scanf("%d", &n)){num_fac = 0;prime_factor(n);printf("%d=", n);for (int i = 0; i < num_fac; i++){if (i > 0)printf("*");printf("%d", fac[i].x);if (fac[i].count > 1)printf("^%d", fac[i].count);}printf("\n");}return 0;
}