HOW求两个数的最大公约数?

简介: HOW求两个数的最大公约数?

当你拿到这个题目是不是立马就会有了思路,如果有了,你又会几种方法求解?如果没有求解思路,请把这个题目刻到你的脑子里,自己多想想,多思考;不要一不会就直接搜答案,去看别人的思路,这样是没效果的;下面讲讲我自己的想法:


-------------------------------------------求最大公约数


法1:暴力求解法


解析:


第一步:我们都知道最大公约数必然是<=两个数(暂时定义为m n)之间的最小数;所以我们第一步就要求出两个数之间的最小数(暂时定义为min),怎么求呢?当然是用三目运算符啦!!!


第二步:   当求出两个数的最小数之后,我们就要写一个循环,让两个数都去除以min进行取余


直到满足(m%min == 0  && n%min ==0)就跳出循环;如果没有满足,(min--)重复上面的操作


下面看代码:


48c8c7bd12924f1fa4ddcd8ce0906c0c.png

法2:辗转相除法


解析:假设定义两个变量(m n),m>n时,此时定义个一个变量t,(t=m%n,m=n,n=t);直到循环条件m%n==0跳出循序;当m<n也是没问题的,就是多走了一次循环;


例如:m=25,n=15 ====>m是大于n的,那么m%n==10;此时m=15,n=10;重复操作;


                                                                       m%n==5;   此时m=10,n=5;重复操作;


                                                                       m%n==0;跳出循环


          m=15,n=25 ====>m是小于n的,那么m%n==15;此时m=25,n=15;又和上面一样了!!


下面看代码:



75e60aa0d5f1492fadf3b3d5b2be17a2.png

好啦,目前就是我所知的求最大公约数的两种方法,  第一次写,有错误或者有大佬知道其它好的方法欢迎留言,目前还在学习中;下一次出一个求最小公倍数的算法;目前知道三种方法求解;欢迎一块学习!!!

相关文章
|
8月前
|
算法
给定两个数,求这两个数的最大公约数
给定两个数,求这两个数的最大公约数
|
Serverless
数的阶乘
数的阶乘
84 3
|
3月前
求这两个数的最小公倍数
【10月更文挑战第21天】求这两个数的最小公倍数。
31 4
|
3月前
求两个数的最小公倍数
【10月更文挑战第20天】求这两个数的最小公倍数。
48 4
|
3月前
求这两个数的最大公约数
【10月更文挑战第21天】求这两个数的最大公约数。
21 1
|
8月前
|
算法
容斥原理:能被整除的数
容斥原理:能被整除的数
|
8月前
|
存储
1013 数素数
1013 数素数
46 0
1013 数素数
|
8月前
26.一个正整数如果恰好等于它的因子之和,这个数称为“完数”,如6=1+2+3,求1000以内所有的完数.
26.一个正整数如果恰好等于它的因子之和,这个数称为“完数”,如6=1+2+3,求1000以内所有的完数.
88 0
|
8月前
|
算法 测试技术 C#
【最大公约数 调和级数】2183.统计可以被 K 整除的下标对数目
【最大公约数 调和级数】2183.统计可以被 K 整除的下标对数目
c/c++求两个数的最大公约数(递归版)
c/c++求两个数的最大公约数(递归版)
203 0