This is a simple program to find the Greatest Common Divisor (GCD) of two given positive numbers.

Problem Definition

Suppose you want to find GCD of two numbers – \Large a and \Large b. The C program for GCD has a function called \Large hcf(a, b) which is called recursively until remainder is \Large 0. The function uses the following logic on the given input numbers where a is greater than or equal to \Large b.

\Large \begin{aligned}
&r = a - (a/b * b)
\end{aligned}

Suppose \Large a = 24 and \Large b = 6 than

\large \begin{aligned}
&r = 24 - (24/6 * 6)\\ 
&r = 24 - 24 = 0\\
&r = 0
\end{aligned}

Then the value of \Large b is the GCD which is \Large 6. Note: – number \Large amust be greater than or equal to \Large b.

Flowchart – Program for GCD of Two Numbers

Figure 1 - Flowchart for Program for GCD of Two Numbers
Figure 1 – Flowchart for Program for GCD of Two Numbers

Program Codes – GCD of Two Numbers

#include <stdio.h>
#include <conio.h>
main()
{
    int i,a,b,gcd;
    int hcf();
    /* Read the input numbers */
    printf("Enter Two Numbers To Find GCD:");
    scanf("%d%d",&a,&b);
    /* Compute the GCD for given numbers */
    gcd=hcf(a,b);
    /* Print the Result */
    for(i=0;i<40;i++)
    printf("_");printf("\n\n");
    printf("GCD of %d and %d is %d\n",a,b,gcd);
    for(i=0;i<40;i++)
    printf("_");printf("\n\n");
    system("PAUSE");
    return 0;
}

int hcf(p,q)
{
    int r;
    r=p-(p/q*q);
    if(r==0)
        return(q);
    else
        return hcf(q,r);
}
#include <iostream>
using namespace std;

int hcf(int p, int q)
{
    int r = p % q;
    if (r == 0)
        return q;
    else
        return hcf(q, r);
}

int main()
{
    int a, b, gcd;

    cout << "Enter Two Numbers To Find GCD: ";
    cin >> a >> b;

    gcd = hcf(a, b);

    cout << "\n----------------------------------------\n";
    cout << "GCD of " << a << " and " << b << " is " << gcd << endl;
    cout << "----------------------------------------\n";

    return 0;
}
import java.util.Scanner;

class GCD
{
    static int hcf(int p, int q)
    {
        int r = p % q;
        if (r == 0)
            return q;
        else
            return hcf(q, r);
    }

    public static void main(String[] args)
    {
        int a, b, gcd;
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter Two Numbers To Find GCD: ");
        a = sc.nextInt();
        b = sc.nextInt();

        gcd = hcf(a, b);

        System.out.println("\n----------------------------------------");
        System.out.println("GCD of " + a + " and " + b + " is " + gcd);
        System.out.println("----------------------------------------");

        sc.close();
    }
}
def hcf(p, q):
    r = p % q
    if r == 0:
        return q
    else:
        return hcf(q, r)

a = int(input("Enter first number: "))
b = int(input("Enter second number: "))

gcd = hcf(a, b)

print("\n----------------------------------------")
print(f"GCD of {a} and {b} is {gcd}")
print("----------------------------------------")

The important piece of code in the above source code is the call to \Large hcf(a, b) function and the function \Large hcf(a, b) calling itself recursively.

gcd = hcf(a, b);

The function \Large hcf(a, b)evaluate the current value of \Large a and \Large b, and if the remainder is not equal to \Large 0, it call itself one more time until the remainder becomes \Large 0.

int hcf(p,q) 
{  
    int r; 
    r=p-(p/q*q);  
    if(r==0)  
        return(q);  
    else  
        return hcf(q,r); 
}

Output

The output of the program is given below. When the user enters \Large 24 and \Large 6, the result is \Large 6 which greatest common divisor (GCD) of \Large 24 and \Large 6

         Enter Two Numbers To Find GCD:24 6
          ------------------------------------------
          GCD of 24 and 6 is 6
          ------------------------------------------