Java program for GCD/HCF with Recursion Technique
Greatest Common divisor or GCD/HCF or Highest Common Factor or Greatest Common Factor of two or more integers number when at least one of them is not zero is the largest positive integer that divides the numbers without a remainder. For example, the GCD of two numbers 54 and 24 is :6.
First Method import java.io.*;
public class GCDRecursive
{
private int a, b, g; // Instance variable
public int gcd(int x,int y)
{
while(x!=y)
{
if(x>y)
return gcd(x-y , y);
else
return gcd(x , y-x);
}
return x;
}
public static void main(String args[]) throws IOException
{
int a,b,gcd,lcm;
InputStreamReader in=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(in);
System.out.println("Enter two number");
a = Integer.parseInt(br.readLine());
b = Integer.parseInt(br.readLine());
// Object of class GCDRecursive
GCDRecursive ob=new GCDRecursive();
gcd=ob.gcd(a,b);
System.out.println("GCD="+gcd);
}
}
Output
Enter two number
54
24
GCD=6
Enter two number
10
3
GCD=1
Second Method
import java.util.Scanner;
public class GreatestCommonDivisor {
public static void main(String args[]) {
//int n1 = 366, n2 = 60;
int n1,n2,gcd;
// int hcf = hcf(n1, n2);
Scanner sc=new Scanner(System.in);
System.out.println("Enter Two number");
n1=sc.nextInt();
n2=sc.nextInt();
gcd=greatestCommonDivisor(n1,n2);
System.out.println("G.C.D of %d and %d is %d.", n1, n2, gcd);
}
public static int greatestCommonDivisor(int n1, int n2)
{
if (n2 != 0)
return greatestCommonDivisor(n2, n1 % n2);
else
return n1;
}
}
Output
Enter Two number
54
24
G.C.D of 54 and 24 is 6
More Java program
