最大公约数的计算py
发布网友
发布时间：2022-05-05 07:31
共1个回答
热心网友
时间：2022-04-18 15:32
如果数小的话，用列举法即可
如：（12,18）
12的正约数：1,2,3,4,6,12
18的正约数：1,2,3,6,9,18
所以（12,18）=6
如果数较大的话用辗转相除法：按以下式子循环下去：较大的数=较小的数×a1+n1，较小的数=n1×a2+n2，n1=n2×a3+n3......n（k-2）下标=n（k-1）下标×ak下标+nk下标，直到nk=0时结束，这两个数的最大公约数为n（k-1）下标
例如：（12345,765）
12345=765×16+105
765=105×7+30
105=30×3+15
30=15×2
所以（12345,765）=15
