Largest common factor C The Largest Common Factor LCF for tw

Largest common factor C++

The Largest Common Factor (LCF) for two positive integers n and m is the largest integer that divides both n and m evenly. LCF(n, m) is at least one, and at most m, assuming that n greaterthanorequalto m. Over two thousand years ago, Euclid provided an efficient algorithm based on the observation that, when n mod m notequalto 0, LCF(n, m) = LCF(m, n mod m). Use this fact to write two algorithms to find the LCF for two positive integers. The first version should compute the value iteratively. The second version should compute the value using recursion.

Solution

//iterative program

#include <iostream>
using namespace std;

int main()
{
   int n, m,k;

   cout << \"Enter two positive integers: \";
   cin >> n >> m;

   while(m!=0)//recursive function which finds largest commanfactor of given two numbers
   {
       k=n;
       n=m;
       m=k%m;  
   }

   cout << \"L.C.F is \"<<n<<endl;

   return 0;
}

output:-

Enter two positive integers: 25 5
L.C.F is 5

//recursive program

#include <iostream>
using namespace std;

int lcf(int n1, int n2);

int main()
{
   int n, m;

   cout << \"Enter two positive integers: \";
   cin >> n >> m;

   cout << \"L.C.F is \"<< lcf(n, m);

   return 0;
}

int lcf(int n1, int n2)//recursive function which finds largest commanfactor of given two numbers
{
    if (n2 != 0)
       return lcf(n2, n1 % n2);
    else
       return n1;
}

output:-

Enter two positive integers: 24 6
L.C.F is 6