Greatest common divisor program in java
The greatest common divisor for 2 number is that the largest number that completely divides both.
For example, the GCD of 16, 24 is 8 that is the highest value that completely divides both 16 and 24. GCD is also reffered to HCF (highest common factor).
We'll use Euclid's algorithm to find the GCD of a and b.
Euclid's algorithm
According to Euclid's algorithm, if a = bq + r (q = quotient, r = remainder,
after dividing a by b) and if r is 0 then
gcd(a,b) = b
otherwise,
gcd(a, b) = gcd(b, r) or gcd(a, r)
To understand why is that so, assume that d is the number which divides a and
b.
It means that it can also divide a - bq (directly saying r).
So you can pretty much
understand that d is the factor of a, b as well as r.
Instead of calculating
the gcd(a, b), we can also calculate the gcd(b, r) which has the similar answer as gcd(a, b).
Euclid's algorithm flowchart
let's figure out the gcd of 50 and 60 using Euclid's algorithm
1) a = 50, b = 60 --> (50 = 60 X 0+ 50)
r = a mod b = 50
gcd(a, b) = gcd(b, r) = gcd(60, 50), since r is not 0
2) a = 60, b = 50 --> (60 = 50 X 1 + 10)
r = a mod b = 10
gcd(a, b) = gcd(b, r) = gcd(50, 10), again r is not 0
3) a = 50, b = 10 --> (50 = 10 X 5 + 0)
r = a mod b = 0
gcd(r, r1) = r1, now r is 0.
4) answer = 10.
Java program to find gcd of two numbers without recursion
import java.util.Scanner;
class Main {
public static void main(String[] args) {
System.out.println("Enter the two numbers:
"); Scanner scan = new Scanner(System.in);
int m = scan.nextInt();
int n =
scan.nextInt();
System.out.println("Gcd: " + gcd(m, n));
}
private static int gcd(int m, int n) {
int r = m % n;
while (r != 0) {
m = n;
n = r;
r = m % n;
}
return n;
}
}
Program output
Enter the two numbers:
16 24
Gcd: 8
Other Recommended Posts
Java program to find the greatest common divisor of two numbers using
recursion
import java.util.Scanner;
class Main {
public static void main(String[] args) {
System.out.println("Enter the two
numbers: ");
Scanner scan = new Scanner(System.in);
int m =
scan.nextInt();
int n =
scan.nextInt();
scan.close();
System.out.println("Gcd: " + gcd(m,
n));
}
private static int
gcd(int a, int b) {
int r = a %
b;
if (r ==
0) return b;
return
gcd(b, r);
}
}
Program output
Enter the two numbers:
20 15
Gcd: 5
