The Greatest Common Divisor (GCD) of two numbers is the greatest number that divides both of them.
GCD Example
Input:63 and 21.
Output:21
Input:10 and 5
Output:5
- In the first case, when we have taken the input of 63 and 21, the output is 21 because 63=7*3*3 and 21=7*3. The common divisors are 7 and 3 and greatest common divisor is 7*3=21.
- In the second case, when we have taken input 10 and 5, the output is 5 because 10=2*5 and 5=1*5. The common divisor is 5 and it is also the greatest one.
Brute Force Approach for GCD
The basic idea is to try all integers from n (where n is the given second number, i.e., the smaller one) down until finding one that divides both the numbers.
Let's take an example of 24 and 12.
- 24%12=0 and 12%12=0. 12 divides both the numbers completely. Therefore, 12 is the GCD of these two numbers.
Another example of 6 and 4.
- 6%4=2 and 4%4=0. 4 doesn't divide both the numbers completely. Therefore, decrementing value by 1(4-1=3).
- 6%3=0 and 4%3=1. 3 doesn't divide both the numbers completely. Therefore, decrementing value by 1(3-1=2).
- 6%2=0 and 4%2=0. 2 divides both the numbers completely. Therefore, 2 is the GCD of these two numbers.
Program
package codesdope;
import java.util.*;
public class codesdope
{
public static int gcd(int num1,int num2,int d)
{
if(num2==0)
return 0;
if(((num1%d)==0) && ((num2%d)==0))
return d;
else
return gcd(num1,num2,num2-1);
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int num1=sc.nextInt();
int num2=sc.nextInt();
System.out.println("gcd is "+gcd(num1,num2,num2));
}
}
63
21
gcd is 21
Let us take an example of of 6 and 4. And, dry run this code-
RECURSIVE CALL | Num1%d | Num2%d | d |
|---|---|---|---|
gcd(6,4,4) | 6%4=2 | 4%4=0 | 4-1=3 |
gcd(6,4,3) | 6%3=0 | 4%3=1 | 3-1=2 |
gcd(6,4,2) | 6%2=0 | 4%2=0 | 2 |
In last, 2 divides 6 and 4 completely. Therefore, 2 is the gcd of these two numbers.
Euclid's Algorithm Approach
The Euclidean algorithm is a way to find the greatest common divisor of two positive integers, a and b. In this approach firstly we divide the greater number with the smaller one. In the next step, we divide the divisor of the previous step with the remainder and continue till we get 0 as remainder.
Let's suppose a is the greater number among a and b. We will proceed like:
Step | Dividend | Divisor | Remainder |
|---|---|---|---|
1 | a | b | c |
2 | b | c | d |
3 | c | d | e |
So, every time we are dividing the divisor of the previous step by the remainder of it. This will continue until we get 0 as remainder.
First, let me show the computations for a=210 and b=45.
- Divide 210 by 45, and get the result 4 with remainder 30, so 210=4*45+30.
- Divide 45 by 30, and get the result 1 with remainder 15, so 45=1*30+15.
- Divide 30 by 15, and get the result 2 with remainder 0, so 30=2*15+0.
- The greatest common divisor of 210 and 45 is 15.
Program
package codesdope;
import java.util.*;
public class codesdope
{
public static int gcd(int num1,int num2)
{
if(num2==0)
return num1;
return gcd(num2,num1%num2);
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int num1=sc.nextInt();
int num2=sc.nextInt();
System.out.println("gcd is "+gcd(num1,num2));
}
}
63
21
gcd is 21
Let us take an example of 6 and 4 and, dry run this code.
RECURSIVE CALL | NUM1 | NUM2 | NUM1%NUM2 |
|---|---|---|---|
gcd(6,4) | 6 | 4 | 6%4=2 |
gcd(4,2) | 4 | 2 | 4%2=0 |
gcd(2,0) | 2 | 0 | - |
