ค้นหา GCD ของตัวเลขสองตัว

ในทางคณิตศาสตร์ ตัวหารร่วมที่ยิ่งใหญ่ที่สุด (GCD) เป็นจำนวนเต็มที่มากที่สุดเท่าที่จะเป็นไปได้ ซึ่งหารจำนวนเต็มทั้งสองได้ เงื่อนไขคือตัวเลขต้องไม่เป็นศูนย์

เราจะทำตามอัลกอริทึมแบบยุคลิดเพื่อค้นหา GCD ของตัวเลขสองตัว

อินพุตและเอาต์พุต

Input:
Two numbers 51 and 34
Output:
The GCD is: 17

อัลกอริทึม

findGCD(a, b)

ป้อนข้อมูล: สองตัวเลข a และ b.

ผลลัพธ์: GCD ของ a และ b.

Begin
   if a = 0 OR b = 0, then
      return 0
   if a = b, then
      return b
   if a > b, then
      return findGCD(a-b, b)
   else
      return findGCD(a, b-a)
End

ตัวอย่าง

#include<iostream>
using namespace std;

int findGCD(int a, int b) {    //assume a is greater than b
   if(a == 0 || b == 0)
      return 0;    //as a and b are 0, the greatest divisior is also 0
   if(a==b)
      return b;    //when both numbers are same
   if(a>b)
      return findGCD(a-b, b);
   else
      return findGCD(a, b-a);
}

int main() {
   int a, b;
   cout << "Enter Two numbers to find GCD: "; cin >> a >> b;
   cout << "The GCD is: " << findGCD(a,b);
}

ผลลัพธ์

Enter Two numbers to find GCD: 51 34
The GCD is: 17