公约数的算法?

来源：学生作业帮助网编辑：作业帮时间：2024/04/28 07:34:52

公约数的算法?
公约数的算法?

公约数的算法?
公约数不存在什么算法,您是不是想问若干个数的最大公约数怎样计算?若是,如下：
常用的方法就是用短除式除：先看这些数,若互质,则他们的最大公约数为1；若不互质,就找出他们的公有质因数,然后用每个数去除以这个公有质因数,一直找找除除,除除找找直到除后商互质,再把所有的公有质因数乘起来,积就是这若干个数的最大公约数；若两个数成倍数关系,则最小公倍数为较小数；
不知能不能懂.加油!不懂的话再问,诚答!

一般地，都是采用短除法：60和30
60 30
------- 2
30 15
------- 3
10 5
------- 5
2 1
2和1已经互质了。然后求公约数=2*3*5=30
这个只是最大公约数，不过有了最大公约数就可以求其他公约数了
补充：审时度势，不一定次次都要用短除。比如60和30.因为30是60的约...

全部展开

一般地，都是采用短除法：60和30
60 30
------- 2
30 15
------- 3
10 5
------- 5
2 1
2和1已经互质了。然后求公约数=2*3*5=30
这个只是最大公约数，不过有了最大公约数就可以求其他公约数了
补充：审时度势，不一定次次都要用短除。比如60和30.因为30是60的约数，所以两者的最大公约数=30
互质两数的最大公约数=1

收起

公约数的算法? 最小公约数的算法? 怎样用算法求a,b的公约数(流程图) 17和18 公约数算法 672/1680 公约数是多少公约数是咋算的欧几里德算法(辗转辗转相除法)所求的公约数为什么是最大公约数RT,我只知道最后的得数一定是两者的公约数,但根据什么证明该公约数必是两者的最大公约数. 20的公约数是什么 245的公约数 5的公约数是什么? 222的最小公约数 1800的公约数求两个数字的最大公倍数和最小公约数的算法是怎么样的?一时不小心打错了 30,18的公约数也是18,12的公约数为什么? 48和54的公约数24,30,72的公约数公约数的形式49和41的公约数形式所有自然数的公约数为( )所有自然数的公约数为( ) 24和48的公约数 6,24的公约数是多少