Naive Approach for GCD of two numbers

Euclidean algorithm for GCD of two numbers:

The basic idea is to find the minimum of the two numbers and find its highest factor which is also a factor of the other number.

Below is the code implementation of the above idea:

C++

// C++ program to find GCD of two numbers\
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return gcd of a and b
int gcd(int a, int b)
{
    // Find Minimum of a and b
    int result = min(a, b);
    while (result > 0) {
        if (a % result == 0 && b % result == 0) {
            break;
        }
        result--;
    }
 
    // Return gcd of a and b
    return result;
}
 
// Driver code
int main()
{
    int a = 98, b = 56;
    cout << "GCD of " << a << " and " << b << " is "
         << gcd(a, b);
    return 0;
}
// This code is contributed by Suruchi Kumari

C

// C program to find GCD of two numbers
 
#include <math.h>
#include <stdio.h>
 
// Function to return gcd of a and b
int gcd(int a, int b)
{
    // Find Minimum of a and b
    int result = ((a < b) ? a : b);
    while (result > 0) {
        if (a % result == 0 && b % result == 0) {
            break;
        }
        result--;
    }
 
    // Return gcd of a and b
    return result;
}
 
// Driver code
int main()
{
    int a = 98, b = 56;
    printf("GCD of %d and %d is %d ", a, b, gcd(a, b));
    return 0;
}
// This code is contributed by Suruchi Kumari

Java

// Java program to find GCD of two numbers
import java.io.*;
 
public class GFG {
 
    // Function to return gcd of a and b
    static int gcd(int a, int b)
    {
        // Find Minimum of a and b
        int result = Math.min(a, b);
        while (result > 0) {
            if (a % result == 0 && b % result == 0) {
                break;
            }
            result--;
        }
 
        // Return gcd of a and b
        return result;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int a = 98, b = 56;
        System.out.print("GCD of " + a + " and " + b
                         + " is " + gcd(a, b));
    }
}
 
// This code is contributed by AnkThon

Python3

# Python program to find GCD of two numbers
 
 
# Function to find gcd of two numbers
def gcd(a, b):
 
    # Find minimum of a and b
    result = min(a, b)
 
    while result:
        if a % result == 0 and b % result == 0:
            break
        result -= 1
 
    # Return the gcd of a and b
    return result
 
 
# Driver Code
if __name__ == '__main__':
    a = 98
    b = 56
    print(f"GCD of {a} and {b} is {gcd(a, b)}")
 
 
# This code is contributed by Soham Mirikar

C#

// C# program to find GCD of two numbers
 
using System;
public class GFG {
     
    // Function to return gcd of a and b
    static int gcd(int a, int b)
    {
        // Find Minimum of a and b
        int result = Math.Min(a, b);
        while (result > 0) {
            if (a % result == 0 && b % result == 0) {
                break;
            }
            result--;
        }
 
        // Return gcd of a and b
        return result;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int a = 98, b = 56;
        Console.WriteLine("GCD of " + a + " and " + b
                          + " is " + gcd(a, b));
    }
}
 
// This code is contributed by AnkThon

Javascript

// Javascript program to find GCD of two numbers
// Function to return gcd of a and b
function gcd(a,b)
{
    // Find Minimum of a and b
    let result = Math.min(a, b);
    while (result > 0) {
        if (a % result == 0 && b % result == 0) {
            break;
        }
        result--;
    }
     
    // Return gcd of a and b
    return result;
}
 
// Driver program to test above function
let a = 98;
let b = 56;
console.log("GCD of ",a," and ",b," is ",gcd(a, b)); 
// This code is contributed by akashish__

Output

GCD of 98 and 56 is 14

Time Complexity: O(min(a,b))
Auxiliary Space: O(1)

Program to Find GCD or HCF of Two Numbers

Given two numbers a and b, the task is to find the GCD of the two numbers.

Note: The GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is the largest number that divides both of them.

Examples:

Input: a = 20, b = 28
Output: 4
Explanation: The factors of 20 are 1, 2, 4, 5, 10 and 20. The factors of 28 are 1, 2, 4, 7, 14 and 28. Among these factors, 1, 2 and 4 are the common factors of both 20 and 28. The greatest among the common factors is 4.

Input: a = 60, b = 36
Output: 12

Recommended PracticeLCM And GCDTry It!

Tags:

#Basic Coding Problems #GCD-LCM #SAP Labs #DSA #Mathematical #SAP Labs #Mathematical