Q. Write a program to find GCD of two numbers.



GCD :- GCD stands for Greatest Common Divisor, GCD of two numbers is the largest number that can exactly divide both numbers. It is also called as HCF.

For Example :-
Input = 20 and 15
Output = 5 is the GCD.
As we can see that 5 divides both 20 and 15 and we don't have any larger number that divides both the numbers therefore, the GCD of 20 and 15 is 5.

GCD Algorithm

START
1. Input 2 Numbers A and B and declare variable GCD which holds the result.
2. Run Loop i from 1 to i <= A and i <=B
    Check if A & B are completely divisible by i or not if yes then
         Assign GCD = i
    Loop End
3. Output GCD 
STOP


GCD Program

  • C
  • C++
  • Java
  • Python
  • C#
  • PHP
    • #include <stdio.h>
int main()
{
int num1=60, num2=45, i, gcd;
for(i=1; i <= num1 && i <= num2; ++i)
{
// Checks if i is factor of both integers
if(num1%i==0 && num2%i==0)
gcd = i;
}
printf("GCD of %d and %d is %d", num1, num2, gcd);
return 0;
}

    #include <bits/stdc++.h>
using namespace std;
int main()
{
int num1=60, num2=45,i,gcd;
for(i=1; i <= num1 && i <= num2; ++i)
{
// Checks if i is factor of both integers
if(num1%i==0 && num2%i==0)
gcd = i;
}
cout << "GCD of "<< num1<<" and "<< num2<<" is "<< gcd;
return 0;
}

    public class LFC
{
public static void main(String args[])
{
int num1 = 60, num2 = 45;
int gcd;
for (int i = 1; i < num1 && i < num2; i++) {
      if (num1 % i == 0 && num2 % i == 0)
        gcd = i;
    }
    System.out.println("GCD of " + num1 +" and " + num2 + " is " + gcd);
}
}

    def find_gcd(num1, num2):
# choose the smaller number
if num1 > num2:
smaller = num2
else:
smaller = num1
for i in range(1, smaller+1):
if((num1 % i == 0) and (num2 % i == 0)):
gcd = i 
return gcd
num1 = 60
num2 = 45
gcd=find_gcd(num1, num2)
print ("G.C.D. of ", num1, " and ", num2, " is ", gcd)

    using System; 
class LFC { 
// Recursive function to return 
// gcd of num1 and num2 
static int find_gcd(int num1, int num2) 
{ 
// Everything divides 0  
if (num1 == 0) 
return num2; 
if (num2 == 0) 
return num1; 
// base case 
if (num1 == num2) 
return num1; 
// num1 is greater 
if (num1 > num2) 
return find_gcd(num1 - num2, num2); 
return find_gcd(num1, num2 - num1); 
} 
// Driver method 
public static void Main()  
{ 
int num1 = 60, num2 = 45; 
Console.WriteLine("GCD of " 
+ num1 +" and " + num2 + " is " 
+ find_gcd(num1, num2)); 
} 
} 

    function find_gcd($num1, $num2) 
{ 
// Everything divides 0  
if ($num1 == 0) 
return $num2; 
if ($num2 == 0) 
return $num1; 
// base case 
if($num1 == $num2) 
return $num1 ; 
// a is greater 
if($num1 > $num2) 
return find_gcd( $num1-$num2 , $num2 ) ; 
return find_gcd( $num1 , $num2-$num1 ) ; 
} 
// Driver code 
$num1 =  60;
$num2 = 45; 
echo "GCD of $num1 and $num2 is ", find_gcd($num1 , $num2) ; 

    #include <stdio.h>
int main()
{
int num1=60, num2=45, i, gcd;
for(i=1; i <= num1 && i <= num2; ++i)
{
// Checks if i is factor of both integers
if(num1%i==0 && num2%i==0)
gcd = i;
}
printf("GCD of %d and %d is %d", num1, num2, gcd);
return 0;
}

    Output

    GCD of 60 and 45 is 15




    Recommended Programs

       Program to find LCM of 2 Numbers.
       Program to find Perfect Number.