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

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

相关文章
|
2月前
|
算法
给定两个数,求这两个数的最大公约数
给定两个数,求这两个数的最大公约数
|
7月前
|
Serverless
数的阶乘
数的阶乘
16 3
|
9月前
|
算法
求1000以内所有的水仙花数
求1000以内所有的水仙花数
|
6月前
628. 三个数的最大乘积
628. 三个数的最大乘积
|
8月前
|
C++
c/c++求两个数的最大公约数(递归版)
c/c++求两个数的最大公约数(递归版)
128 0
|
11月前
|
Python
找几个数的最大乘积
找几个数的最大乘积
42 0
|
11月前
|
索引
三个数的最大乘积
三个数的最大乘积
43 0
|
11月前
|
算法
求水仙花数
求水仙花数
51 0
|
11月前
找出水仙花数
找出水仙花数
51 0
|
12月前
7-150 水仙花数
7-150 水仙花数
36 0