Skip to main content

Euclidean Algorithm in Bash

· One min read
ひかり
ひかり
Main bloger

  1. Let C be the remainder when A is divided by B.

  2. Let D be the remainder when B is divided by C.

  3. Let E be the remainder when C is divided by D.

    ...

  4. Let Y be the remainder when X is divided by 0.

    Then Y is the greatest common divisor.

Bash Script

#!/usr/bin/env bash

function gcd(){
   test $2 -eq 0 && echo $1 || gcd $2 $(( $1 % $2 ))
}

gcd 1071 1029
# 21