偶几里得算法

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。即设两个数进行相除（大的除以小的）然后用小的那个数除以余数，再用小的除以得到的余数，一直相除，最后余数为零为止，即最后一次相除的两个数中较小的那个即为最大公约数

伪代码

read num1
read num2
set r=num1%num2
while （r！=0）
set num1 to num2
set num2 to r
set r=num1%num2
write num2

测试