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



GCD :- GCD is the greatest common divisor of two numbers is the largest number that divides them both.
For Example :-
Input = 20 and 15
Output = 5 is the GCD.
So as we can see that 5 divides both 20 and 15 and does not have any large number having this properties i.e the GCD of 20 and 15 is 5.

GCD Algorithm

START
    if a = 0 OR b = 0, then
      return 0
   if a = b, then
      return b
   if a > b, then
      return findGCD(a-b, b)
   else
      return findGCD(a, b-a)
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("G.C.D 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 << "G.C.D of "<< num1<<" and "<< num2<<" is "<< gcd;
        return 0;
    }
    
    public class LFC
    {
        public static void main(String args[])
        {
            char ch='P';
        
            if(ch=='a' || ch=='A' || ch=='e' || ch=='E' ||
            ch=='i' || ch=='I' || ch=='o' || ch=='O' ||
            ch=='u' || ch=='U')
            {
                System.out.printf("%c is a Vowel",ch);
            }
            else
            {
                System.out.printf("%c is a Consonant",ch);
            }
        }
    }
    
    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("G.C.D of %d and %d is %d", num1, num2, gcd);
    
        return 0;
    }

    Output

    G.C.D of 60 and 45 is 15
    
    

    Recommended Programs

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