Go Program to Find HCF of Two Numbers

In Go, you can find the HCF of two numbers using Euclid's algorithm with a function like func hcf(a, b int) int { for b != 0 { a, b = b, a % b } return a } which repeatedly replaces numbers until the remainder is zero.

Examples

Inputa=12, b=18

Output6

Inputa=100, b=25

Output25

Inputa=7, b=3

Output1

How to Think About It

To find the HCF of two numbers, think about the largest number that divides both without leaving a remainder. Euclid's algorithm helps by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller until the remainder is zero. The last non-zero remainder is the HCF.

Algorithm

1

Get two numbers as input.

2

While the second number is not zero, do:

3

Replace the first number with the second number.

4

Replace the second number with the remainder of the first number divided by the second number.

5

When the second number becomes zero, the first number is the HCF.

6

Return the first number.

Code

go

package main

import "fmt"

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

func main() {
    a, b := 12, 18
    fmt.Printf("HCF of %d and %d is %d\n", a, b, hcf(a, b))
}

Output

HCF of 12 and 18 is 6

Dry Run

Let's trace the example where a=12 and b=18 through the code.

1

Initial values

a = 12, b = 18

2

First iteration

a, b = 18, 12 % 18 = 18, 12

3

Second iteration

a, b = 12, 18 % 12 = 12, 6

4

Third iteration

a, b = 6, 12 % 6 = 6, 0

5

Loop ends

b is 0, so return a = 6

a	b
12	18
18	12
12	6
6	0

Why This Works

Step 1: Using Euclid's Algorithm

The algorithm uses the fact that the HCF of two numbers also divides their difference or remainder.

Step 2: Loop until remainder zero

We keep replacing the pair with (b, a % b) until the remainder (b) becomes zero.

Step 3: Return last non-zero remainder

When remainder is zero, the other number (a) is the HCF.

Alternative Approaches

Recursive Euclid's Algorithm

go

package main

import "fmt"

func hcf(a, b int) int {
    if b == 0 {
        return a
    }
    return hcf(b, a % b)
}

func main() {
    a, b := 12, 18
    fmt.Printf("HCF of %d and %d is %d\n", a, b, hcf(a, b))
}

This uses recursion instead of a loop, which is elegant but may use more stack space.

Brute Force Method

go

package main

import "fmt"

func hcf(a, b int) int {
    min := a
    if b < a {
        min = b
    }
    for i := min; i > 0; i-- {
        if a%i == 0 && b%i == 0 {
            return i
        }
    }
    return 1
}

func main() {
    a, b := 12, 18
    fmt.Printf("HCF of %d and %d is %d\n", a, b, hcf(a, b))
}

This checks all numbers from min(a,b) down to 1, which is simple but slower for large numbers.

Complexity: O(log(min(a,b))) time, O(1) space

Time Complexity

Euclid's algorithm runs in logarithmic time relative to the smaller input because each step reduces the problem size significantly.

Space Complexity

The iterative version uses constant extra space, only storing a few variables.

Which Approach is Fastest?

The iterative Euclid's algorithm is fastest and most memory efficient compared to recursion or brute force.

Approach	Time	Space	Best For
Iterative Euclid's Algorithm	O(log(min(a,b)))	O(1)	Efficient and simple for all inputs
Recursive Euclid's Algorithm	O(log(min(a,b)))	O(log(min(a,b)))	Elegant code but uses stack space
Brute Force Method	O(min(a,b))	O(1)	Simple but slow for large numbers