Euclidean Algorithm

Definition

Definition

The Euclidean Algorithm is a method for finding the greatest common divisor (GCD) of two integers. It relies on the principle that the GCD of two numbers remains the same if the larger number is replaced by its difference with the smaller number. This process continues until one of the numbers becomes zero, at which point the other number is the GCD

Explanation

Select two non-negative integers, denoted as a and b. If b equals zero, the greatest common divisor (GCD) of a and b is a. Otherwise, repeatedly apply the algorithm with b as the new a and a modulo b as the new b until b reaches zero. Finally, return the value of a as the GCD

Guidance

• Take two non-negative integers a and b
  • if b is 0, the GCD is a
    • return a
  • otherwise, find the remainder of a divided by b
  • replace a with the value of b, and b with the remainder found in the previous step
  • repeat steps until b becomes zero
• Return the value of a, which is the GCD

Tips

• ensure to handle the case where one of the inputs is zero
• optimize the algorithm by using iterative instead of recursive implementation for better performance
• validate inputs to handle negative integers appropriately

Practice

Practice

euclideanAlgorithm(a, b)
  while b is not zero
    temp := b
    b := a % b
    a := temp
  return a

Solution

package main

// recursive
func euclideanRecursive(a, b int) int {
    if b == 0 {
        return a
    }
    return euclideanRecursive(b, a%b)
}

// iterative
func euclideanIterative(a, b int) int {
    var temp int
    for b != 0 {
        temp = b
        b = a % b
        a = temp
    }
    return a
}

public class EuclideanAlgorithm {

  // recursive
  public static int euclideanRecursive(int a, int b) {
    if (b == 0) {
      return a;
    }
    return euclideanRecursive(b, a % b);
  }

  // iterative
  public static int euclideanIterative(int a, int b) {
    int temp;
    while (b != 0) {
      temp = b;
      b = a % b;
      a = temp;
    }
    return a;
  }
}

// recursive
function euclideanRecursive(a, b) {
  if (b === 0) {
    return a;
  }
  return euclideanRecursive(b, a % b);
}

// iterative
function euclideanIterative(a, b) {
  let temp;
  while (b !== 0) {
    temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

// recursive
fun euclideanRecursive(a: Int, b: Int): Int {
    return if (b == 0) a else euclideanRecursive(b, a % b)
}

// iterative
fun euclideanIterative(a: Int, b: Int): Int {
    var temp: Int
    var aa = a
    var bb = b
    while (bb != 0) {
        temp = bb
        bb = aa % bb
        aa = temp
    }
    return aa
}

# recursive
def euclidean_recursive(a, b):
    return a if b == 0 else euclidean_recursive(b, a % b)

# iterative
def euclidean_iterative(a, b):
    while b != 0:
        a, b = b, a % b
    return a

// recursive
fn euclidean_recursive(mut a: i32, mut b: i32) -> i32 {
    if b == 0 {
        return a;
    }
    return euclidean_recursive(b, a % b);
}

// iterative
fn euclidean_iterative(mut a: i32, mut b: i32) -> i32 {
    let mut temp: i32;
    while b != 0 {
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// recursive
function euclideanRecursive(a: number, b: number): number {
  return b === 0 ? a : euclideanRecursive(b, a % b);
}

// iterative
function euclideanIterative(a: number, b: number): number {
  let temp: number;
  while (b !== 0) {
    temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}