Recursive method to find the greatest common divisor and the least common multiple of the code

  • 2020-04-01 23:34:14
  • OfStack


              Mathematical principle:

            Let's say we have two Numbers, num1 and num2, and let's say num1 is large. Let the remainder r = num1 % num2.
            When r == 0, num1 is divisible by num2, and obviously num2 is the largest common divisor of these two Numbers.
            When r! When = 0, let num1 = num2 (divisor to dividend), num2 = r (remainder to divisor), then r = num1 % num2. Recursively, all the way to r equals zero.
            The above mathematical principle can do an analysis with specific two Numbers, so easy to understand.

Code implementation (find the greatest common divisor) :


#include <iostream>
using namespace std;
int gcd(int a, int b);//Declare the greatest common divisor function
int main()
{
    int num1 = 1;
    int num2 = 1;    
    cin >> num1 >> num2;
    while(num1 == 0 || num2 == 0)//Determine whether a 0 value is entered, and if so, re-enter
    {
        cout << "input error !" << endl;
        cin >> num1 >> num2;
    }
    cout << "The gcd of " << num1 << " and " << num2 << " is: " << gcd(num1, num2) << endl;//Call the greatest common divisor function
    return 0;
}
int gcd(int a, int b)//The function definitions
{
    int max = a > b ? a : b;
    int min = a < b ? a : b;
    a = max;
    b = min;
    int r = a % b;
    if(0 == r)//If a is divisible by b, then b is the greatest common divisor.
        return b;
    else
        return gcd(b, r);//Recursive & have spent & have spent & have spent
}

The method of finding the least common multiple is based on the method of finding the greatest common divisor. Because the least common multiple is equal to the product of two Numbers over the greatest common divisor.

Code implementation (find the least common multiple) :

#include <iostream>
using namespace std;
int gcd(int a, int b);//Declare the greatest common divisor function
int main()
{
    int num1 = 1;
    int num2 = 1;    
    int lcm = 1;
    cin >> num1 >> num2;
    while(num1 == 0 || num2 == 0)//Determine whether a 0 value is entered, and if so, re-enter
    {
        cout << "input error !" << endl;
        cin >> num1 >> num2;
    }
    lcm = num1 / gcd(num1, num2) * num2;//Dividing before multiplying can prevent large Numbers to some extent
    cout << "The lcm of " << num1 << " and " << num2 << " is: " << lcm << endl;
    return 0;
}
int gcd(int a, int b)//The function definitions
{
    int max = a > b ? a : b;
    int min = a < b ? a : b;
    a = max;
    b = min;
    int r = a % b;
    if(0 == r)//If a is divisible by b, then b is the greatest common divisor.
        return b;
    else
        return gcd(b, r);//Recursive & have spent & have spent & have spent
}

The above is the maximum common divisor and the minimum common multiple of the two books. It remains to be proved whether the method is still applicable when there are many Numbers.


Related articles: