1059 Prime Factors (25分)【质因数分解】

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​​​k​1​​​​×p​2​​​k​2​​​​×⋯×p​m​​​k​m​​​​.

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​​^k​1​​*p​2​​^k​2​​*…*p​m​​^k​m​​, where p​i​​'s are prime factors of N in increasing order, and the exponent k​i​​ is the number of p​i​​ -- hence when there is only one p​i​​, k​i​​ is 1 and must NOT be printed out.

Sample Input:

97532468

Sample Output:

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

解题思路：

这道题给我们一个int范围的整数n，按照从小到大的顺序输出其质因数分解的结果。这其实就是一道很普通的质因数分解板子题。我们先打好一个素数表，然后用一个结构体来保存质因子数。然后题目中说是int范围内的正整数进行质因子分解，因此我们的素数表大概开就可以了。

#include<iostream>
#include<math.h>
using namespace std;
struct factor {int num;int cnt;
}fac[10];int prime[100010], pNum = 0;int isPrime(int n)   //判断是否是素数
{if (n <= 1)return 0;for (int i = 2; i <= sqrt(n); i++){if (n%i == 0)return 0;}return 1;
}void primeTable()
{for (int i = 0; i < 100010; i++){if (isPrime(i) == 1)prime[pNum++] = i;}
}int main()
{primeTable();      //先打好表int n;int count = 0;     //记录质因子的个数cin >> n;if (n == 1)            //注意特殊情况cout << "1=1" << endl;else {cout << n << "=";for (int i = 0;prime[i] <= sqrt(n); i++){if (n%prime[i] == 0){fac[count].num = prime[i];fac[count].cnt = 0;while (n%prime[i] == 0){n /= prime[i];fac[count].cnt++;}count++;          //质因子个数加1}if (n == 1)break;      //及时退出}if (n != 1)     //注意如果不能被根号n里的数整除，那么就一定有一个大于根号n的质因子{fac[count].num = n;fac[count++].cnt = 1;}//输出结果for (int i = 0; i < count; i++){cout << fac[i].num;if (fac[i].cnt > 1)cout << "^" << fac[i].cnt;if (i<count-1)cout << "*";}}return 0;
}