Introduction to Programming (I)

Lab 6-2: 最大公因數 (35%)

Euclidean algorithm - Wikipedia

可以參考以下 pseudocode：

while a != b 
    if a > b
        a = a - b
    else
        b = b - a
return a

• 輸入：
  • 兩自然數字 \( a, b \) 並且各自不多於 18 位數字。
  • 需偵測不合法的輸入，並輸出 Invalid input 。
  • 需支援重複輸入，使用者輸入 0 則結束程式。
• 輸出：兩自然數字 \( a, b \) 的最大公因數 \( gcd(a, b) \)。
• 檔名：lab6_2_<學號>.cpp (e.g. lab6_2_106062802.cpp)

程式需提示使用者輸入兩數字 \( a, b \)，輸出兩數字 \( a, b \) 的最大公因數 \( gcd(a, b) \)。 使用者會在每次輸入時輸入任意整數，請考慮所有合法 long long 型態的數字輸入。

The number a (input 0 to exit): <a>⏎
The number b (input 0 to exit): <b>⏎
The gcd(a, b) = <gcd(a, b)>

Example:

$ ./a.out
The number a (input 0 to exit): 15⏎
The number b (input 0 to exit): 17⏎
The gcd(a, b) = 1

The number a (input 0 to exit): 16⏎
The number b (input 0 to exit): 8⏎
The gcd(a, b) = 8

The number a (input 0 to exit): 16⏎
The number b (input 0 to exit): 0⏎

$ ./a.out
The number a (input 0 to exit): -1⏎
Invalid input
The number a (input 0 to exit): 16⏎
The number b (input 0 to exit): -1⏎
Invalid input
The number a (input 0 to exit): 0⏎

Reference Code:

Credit: 藍珮芳(110021116)

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main(int argc, char **argv)
{
	long long int a, b, gcd;
	int i = 0, j = 0, k = 0;

	while (true)
	{
		cout << "The number a (input 0 to exit): ";
		cin >> a;
		if (a >= (long long int)pow(10, 18) || a < 0)
		{
			cout << "Invalid input\n";
			continue;
		}
		if (a == 0)
			return 0;

		cout << "The number b (input 0 to exit): ";
		cin >> b;
		if (b >= (long long int)pow(10, 18) || b < 0)
		{
			cout << "Invalid input\n";
			continue;
		}
		if (b == 0)
			return 0;
		while (a != 0 && b != 0)
		{
			if (a >= b)
			{
				a = a % b;
			}
			else
			{
				b = b % a;
			}
		}
		if (a >= b)
			gcd = a;
		else
			gcd = b;
		cout << "The gcd(a, b) = " << gcd << "\n\n";
	}
}