求公因数的Python程序实现

求公因数欧几里得的这个算法（Euclid’s Algorithm），如用表达式表达，则是：

图1-88是子程序，用以实现上述花括弧内的算法。对其中图1-88a到了余数zz（DM7、VW8、D7或remainder）为0时，即EQ或pEQON时，则输出公因数。否则，一直进行相应运算。这里xx，yy为形式参数。调子程序前用x，y对其赋值。

图1-88 求两个整数的公因数子程序

提示：DIV指令为整除运算指令。如图1-88a，其商存于DM6中，而余数存于DM7中。如图1-88b，其商存于VW6中，而余数存于VW8中。如图1-88c，其商存于D6中，而余数存于D7中。故判断DM7或VW8或D7是否为0，即可知道YY能否XX整除。图1-88d节1为求“模”运算。目的是得到余数。节2是判断得到的余数是否为0。节3、4是如果余数为0，输出结果（Comma Factor），并返回主程序。节5如果余数（remainder）不为0，变换求“模”运算数据，为下一次计算准备。(www.xing528.com)

图1-89所示主程序，用以实现上述花括弧外的算法。AA为求解起动信号，一旦它ON，将使pAAON一个扫描周期，并用它去起动bAA或call_calculate，进而调上述子程序。直到EQ或图1-89d的pEQON（即zz=0），并通过pEQ使bAA或call_calculate OFF，则退出子程序调用。图1-89d的pEQ不是微分输出，所以，图1-89d第1节增加了它的复位操作，即call_calculate OFF后，如pEQON，自身将复位。这也为新的计算做准备。

图1-89 求两个整数的公因数主程序

提示：图1-89程序用了微分指令及bAA或call_calculate的自保持功能，目的是确保在pEQOFF，即yy未能被xx整除时，子程序一直在调用。而到了EQON，即yy能被xx整除时，又可使bAA OFF，子程序停止调用。在多周期完成运算的情况下，这么处理是很方便的。