a695 - [NOIP 2012 普及組] 1.分解质因数

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個正整數 n，已知 n 是兩個不同質數的乘積，要求輸出較大的那個質數。

解題思路

由於題目保證 n 是兩個不同質數的乘積，因此我們可以從 2 開始迭代到 sqrt(n)，尋找 n 的一個因數 i。如果找到一個因數 i，那麼 n / i 就是另一個因數。接著，我們需要驗證 n / i 是否為質數。驗證方法是從 2 迭代到 sqrt(n / i)，如果 n / i 能被任何數整除，則它不是質數。如果 n / i 是質數，那麼它就是較大的質數，直接輸出即可。

複雜度分析

• 時間複雜度: O(sqrt(n)^2) 最壞情況下，需要迭代到 sqrt(n) 尋找因數，然後再迭代到 sqrt(n/i) 驗證是否為質數。
• 空間複雜度: O(1) 只使用了常數級別的額外空間。

程式碼

#include <iostream>
#include <cmath>

using namespace std;

int main(){
	
	long long int a,b=0;
	bool d=true;
	while(cin >> a){
		for(int i=2;i<=sqrt(a);i++){
			if(a%i==0){
				b=a/i;
				for(int j=2;j<=sqrt(b);j++){
					if(b%j==0){
						d=false;
						break;
					}
				}
				if(d==true){
					cout << b << endl;
				}
				d=true;
			}
		}
	}
}