Find HCF or GCD in Go

In this tutorial, we will learn how to find the Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two numbers in Go. We will cover the basic concept and implement functions using both the math library and the Euclidean algorithm.

What is HCF or GCD

The Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers without leaving a remainder. For example, the HCF/GCD of 8 and 12 is 4.

Syntax

The syntax to find the HCF or GCD of two numbers in Go can be done in two ways:

import (
    "fmt"
    "math"
)

func gcdUsingMath(a, b int) int {
    return int(math.Gcd(float64(a), float64(b)))
}

func gcdUsingEuclidean(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }
    return a
}

Example 1: Finding the HCF or GCD of two numbers using the math library

We can use the built-in math library in Go to find the HCF or GCD of two numbers.

For example,

  1. Import the fmt and math packages.
  2. Define a function named gcdUsingMath that takes two parameters a and b of type int.
  3. Use the math.Gcd function to find the HCF or GCD of the two numbers.
  4. Return the result as an integer.
  5. In the main function, call the gcdUsingMath function with sample values and print the result.

Go Program

package main

import (
    "fmt"
    "math"
)

func gcdUsingMath(a, b int) int {
    return int(math.Gcd(float64(a), float64(b)))
}

func main() {
    // Find the HCF/GCD of 8 and 12 using the math library
    result := gcdUsingMath(8, 12)

    // Print the result
    fmt.Printf("HCF/GCD of 8 and 12 using math library is %d\n", result)
}

Output

HCF/GCD of 8 and 12 using math library is 4

Example 2: Finding the HCF or GCD of two numbers using the Euclidean algorithm

We can use the Euclidean algorithm to find the HCF or GCD of two numbers by iterating through the modulo operation.

For example,

  1. Define a function named gcdUsingEuclidean that takes two parameters a and b of type int.
  2. Use a for loop to iterate until b becomes zero.
  3. In each iteration, set a to b and b to a % b.
  4. Return the value of a after the loop ends.
  5. In the main function, call the gcdUsingEuclidean function with sample values and print the result.

Go Program

package main

import (
    "fmt"
)

func gcdUsingEuclidean(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }
    return a
}

func main() {
    // Find the HCF/GCD of 8 and 12 using the Euclidean algorithm
    result := gcdUsingEuclidean(8, 12)

    // Print the result
    fmt.Printf("HCF/GCD of 8 and 12 using Euclidean algorithm is %d\n", result)
}

Output

HCF/GCD of 8 and 12 using Euclidean algorithm is 4