a024 - 最大公因數(GCD)

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算兩個給定整數的最大公因數 (GCD)。輸入包含兩個整數，以空白分隔。輸出這兩個整數的最大公因數。

解題思路

此程式碼使用暴力法來尋找兩個整數的最大公因數。它從 1 迭代到兩個數中較小的數，並檢查當前迭代的數字是否能同時整除這兩個數。如果可以，則將其儲存為當前 GCD。迴圈結束後，儲存的 GCD 就是兩個輸入整數的最大公因數。

複雜度分析

• 時間複雜度: O(min(a, b))
• 空間複雜度: O(1)

程式碼

#include <iostream>

using namespace std;


int main(){
	
	int GCD,a,b;
		while(cin>>a>>b){
			for(int i=1;i<=a&&i<=b;i++){
				if(a%i==0&&b%i==0){
					GCD=i; 
				}	
			}
	cout<<GCD<<endl;
	}

}