유클리드 순서도

유클리드 알고리즘을 이용하여 두 자연수 $a$, $b$의 최대공약수를 구하는 방법은 다음과 같다. 두 수 $a$, $b$의 최대공약수를 $d$라고 하면 $d$는 $a$와 $b$를 동시에 나누므로, $d$는 $a - b$와 $b$를 나누게 된다. 이와 같은 방법으로 $a < b$이면 $a$와 $b - a$의 최대공약수를 알아보고, $a > b$이면 $a - b$와 $b$의 최대공약수를 구하면 된다. 따라서, (가)에 들어가는 식은 $\square {\begin{aligned} a \leftarrow a - b \\ b \leftarrow b \end{aligned}}$이다. 이를 이용하여 2004, 1670의 최대공약수를 구해 보면 다음과 같다. ($a$, $b$)=(2004, 1670) ($a > b$) =(334, 1670) ($a < b$) =(334, 1336) ($a < b$) =(334, 1002) ($a < b$) =(334, 668) ($a < b$) =(334, 334) ($a = b$) =334 따라서, 인쇄되는 $b$의 값은 334이다.