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.