The Largest Common Factor LCF for two positive integers n an

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

First Version : Iteration -

import java.util.*;

public class LargestCommonFactor {

   public static void main(String[]args){

      int a,b;

      int hcf;

      Scanner sc = new Scanner(System.in);

      System.out.println(\"Enter your first number: \");

      a= sc.nextInt();

      System.out.println(\"Enter your second number: \");

      b=sc.nextInt();

      if(b>a) {

      System.out.println(\"Wrong Input the first number must be larger than the second one\");

      } else {

         hcf = b;

         for (; hcf > 0; hcf--) {

          if ((a % hcf == 0) && (b % hcf == 0)) {

          break;

          }

         }

         System.out.println(\"The H.C.F of \"+a+\" and \"+b+\" is: \" + hcf);

      }   

   }

}

Second Version : Recursion -

import java.util.*;

public class LargestCommonFactor {

      int HCF(int a,int b){

      int c;

      c=a%b;

      if(c==0)

      return b;

      else

      return HCF(b,c);

}

   public static void main(String[]args){

      int a,b;

      Scanner sc = new Scanner(System.in);

      System.out.println(\"Enter your first number: \");

      a= sc.nextInt();

      System.out.println(\"Enter your second number: \");

      b=sc.nextInt();

      LargestCommonFactor obj= new LargestCommonFactor();

      if(b>a)

      System.out.println(\"Wrong Input the first number must be larger than the second one\");

      else

      System.out.println(\"The H.C.F of \"+a+\" and \"+b+\" is: \" + obj.HCF(a,b));

      }

}