求最大公约数,最重要就是求出多个整数的共同因数。回忆一下,如何求1个整数包含所有的因数,要用到那些运算符?
输入两个非0正整数,输出它们最大的公约数。请写程序实现。
求两个整数的最大公约数方法与求一个整数的因数方法相似,都是用试商的方法。不同地方是求最大公约数时,试商要同时去除两个整数。只有两个整数都能整除试商值。那这个数就是最大公约数。由于是求最大的公约数,所以试商时可以从较小那个整数开始。
flowchart LR A(开始程序) --> B[/输入两个整数a,b/] B --> C[c=min#40;a,b#41;] C --> D{a%c!=0 或
b%c!=0 } D -- Yes --> E[c=c-1] E --> D D -- No --> F[/输出c值/] F -->G(结束程序)
思考一下,c=min(a,b)作用是什么?