a010 - 因數分解

🔗 前往 ZeroJudge 原題

題目描述

題目要求將輸入的整數分解成質數的乘積，並以指定格式輸出。例如，12 應輸出為 2^2 * 3，質數本身則直接輸出，如 17。

解題思路

此題的核心是質因數分解。程式從 2 開始迭代，嘗試將輸入數字 a 除以當前迭代的數字 i。如果 a 可以被 i 整除，則 i 是一個質因數。程式會持續將 a 除以 i，直到 a 不再能被 i 整除。在此過程中，記錄 i 作為因數出現的次數 j。如果 j 大於 1，則以 i^j 的形式輸出因數。如果 j 等於 1，則直接輸出 i。迭代過程中，如果 a 不等於 i 且 a 不等於 1，則在因數之間輸出 " * "。最後，如果 a 仍然大於 1，則 a 本身是一個質因數，直接輸出。

複雜度分析

• 時間複雜度: O(sqrt(n))，其中 n 是輸入數字。因為程式迭代到 sqrt(n) 即可完成質因數分解。
• 空間複雜度: O(1)，程式使用固定的額外空間。

程式碼

#include <iostream>
 int main (){
 	int a,j;
 	while(std::cin >> a){
 		for(int i=2,b=a;i<=b;i++){//20=2*2*5
 			if(a%i==0){
 				for(std::cout << i ,a/=i,j=1;a%i==0;j++,a/=i){}
				(j>1)?printf("^%d",j):1;
				(a!=i && a!=1)?printf(" * "):printf("\n");
			}
		}
	 }
 }