Mathematical Problemseasy
0 views

HCF/GCD of Two Numbers

Find the highest common factor (HCF) or greatest common divisor (GCD) of two given positive integers.

Understand the Problem

Problem Statement

The program must accept two numbers X and Y and then print their HCF/GCD.

Input Format:
The first line denotes the value of X.
The second line denotes the value of Y.

Output Format:
The first line contains the HCF of X and Y.

Constraints

  • 1 <= X <= 999999
  • 1 <= Y <= 999999
  • Both X and Y are positive integers
  • Program must handle large numbers efficiently

Examples

Example 1
Input
30
40
Output
10
Explanation
The factors of 30 are 1, 2, 3, 5, 6, 10, 15, 30.
The factors of 40 are 1, 2, 4, 5, 8, 10, 20, 40.
The highest common factor is 10.
Example 2
Input
15
10
Output
5
Explanation
The factors of 15 are 1, 3, 5, 15.
The factors of 10 are 1, 2, 5, 10.
The highest common factor is 5.
Example 3
Input
48
18
Output
6
Explanation
Using Euclidean algorithm:
48 % 18 = 12
18 % 12 = 6
12 % 6 = 0
So HCF is 6.

Solution

#include <stdio.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int x, y;
    scanf("%d", &x);
    scanf("%d", &y);
    
    printf("%d", gcd(x, y));
    return 0;
}
Time:O(log min(X, Y)) - The number of iterations is logarithmic in the smaller number
Space:O(1) - Uses only constant extra space for variables
Approach:

Step-by-step explanation:

  1. Function gcd(): Implements Euclidean algorithm
  2. While loop: Continues until b becomes 0
  3. temp variable: Stores original value of b before updating
  4. Modulo operation: a % b finds remainder
  5. Variable swap: a becomes old b, b becomes remainder
  6. Return value: When b is 0, a contains the GCD
  7. main(): Reads input and calls gcd function

Visual Explanation

Loading diagram...
All ProblemsMore Mathematical Problems