Find GCD (Greatest Common Divisor) in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

  

C Program

#include<stdio.h>

int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    while (b) {
        int t = b;
        b = a % b;
        a = t;
    }
    printf("%d", a);
}

C Output

Input: 48 18  
Output: 6

C++ Program

#include<iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    while (b) {
        int t = b;
        b = a % b;
        a = t;
    }
    cout << a;
}

C++ Output

Input: 56 98  
Output: 14

JAVA Program

import java.util.*;

class G {
    public static void main(String[] a) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt(), y = sc.nextInt();
        while (y != 0) {
            int t = y;
            y = x % y;
            x = t;
        }
        System.out.print(x);
    }
}

JAVA Output

Input: 60 48  
Output: 12

Python Program

a, b = map(int, input().split())
while b:
    a, b = b, a % b
print(a)

Python Output

Input: 81 27  
Output: 27

In-Depth Learning – Full Concept in Paragraphs

What Is GCD?

Greatest Common Divisor (GCD) of two numbers is the greatest number which divides both of them with no remainder. The GCD of 18 and 48 would be 6, as 6 is the greatest number which can divide them exactly. GCD is a basic number theory concept and is used in reducing fractions, solving Diophantine equations, and algorithms that need optimization of values.

How Does the Code Work?

The Euclidean Algorithm logic employed here is one of the oldest and most effective algorithms to determine GCD. It is a straightforward principle:

GCD(a, b) = GCD(b, a % b)

We keep on performing this operation by substituting a with b and b with a % b until b is 0. At that time, the value of a will be the GCD.

This is very much efficient, even for large integers, because in every step the size of the problem is decreased using modulus.

Example

Let's calculate GCD of 48 and 18:

Step 1: a = 48, b = 18 → 48 % 18 = 12

Step 2: a = 18, b = 12 → 18 % 12 = 6

Step 3: a = 12, b = 6 → 12 % 6 = 0

Result: GCD = 6

The same method applies to any two numbers, whether one is greater than the other or both are equal.

Real-Life Analogy

Consider two individuals with varying numbers of tiles and wish to make the biggest equal square tiles out of them with no remainder. The side of such a square tile would be their GCD. Suppose one has 48 tiles and the other 18, then both can each make 6 squares of 6 tiles with no remainder. This conveys GCD as the largest equal sized unit common to both.

Why GCD Matters

GCD is applied in simplifying fractions to their lowest terms. For instance, 18/48 reduces to 3/8 when both the numerator and the denominator are divided by their GCD (6). It's also applied in cryptography, digital signal processing, game development (collision detection), and wherever ratios and proportions are required.

It is also the foundation of higher-level mathematical ideas such as LCM (Least Common Multiple), modular arithmetic, and coprime number testing. In programming interviews, GCD questions are frequently used to test recursion, loop, and efficient computation knowledge.

Python-Specific Benefit

Python has a very neat manner of coding the GCD logic using tuple unpacking (a, b = b, a % b) in one line. It's expressive, yet concise, and has the same logic as the standard Euclidean method. For newcomers, this method enhances variable update understanding simultaneously.

SEO-Optimized Natural Paragraph for Ranking

If you need the quickest and simplest method to compute the GCD of two integers, this tutorial provides you with straightforward and simple solutions in C, C++, Java, and Python. Whether you're practicing coding interview questions, online tests, or college homeworks, the Euclidean algorithm assists you to compute the GCD problem quickly and accurately. The samples used are accessible to beginners, but the application carries over to everyday problem-solving and higher-level computer science problems. Knowing how to compute GCD is a key to reducing ratios, dealing with integer relationships, and becoming proficient in basic programming concepts.