The Largest Common Factor (LCF) for two positive integers n and m is the largest
ID: 3775146 • Letter: T
Question
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.Explanation / Answer
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));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.