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;
}