精华内容
下载资源
问答
  • m = 9147485 n = 5147480 辗转相除法求最大公约数 最大公约数=?
  • 主要介绍了Java中使用辗转相除法求最大公约数,本文直接给出代码实例,需要的朋友可以参考下
  • 辗转相除法求最大公因数

    千次阅读 2020-12-20 18:59:12
    辗转相除法求最大公因数 辗转相除法求最大公因数的一种方法,其原理和更相减损术有异曲同工之处,所以可以由更相减损术的原理引入辗转相除法的原理。 更相减损术的原理 假设现有两个数161和63,要求这两个数的最大...

    辗转相除法求最大公因数

    辗转相除法是求最大公因数的一种方法,其原理和更相减损术有异曲同工之处,所以可以由更相减损术的原理引入辗转相除法的原理。

    更相减损术的原理

    假设现有两个数16163,要求这两个数的最大公因数,先假定最大公因数为a,可以将161看作63+98,63与98的和161可以被a整除,其中63也可以被a整除,自然98可以被a整除;

    因此这个问题转化为求9863的最大公因数a;

    98可以看作63+35,63和35的和98可以被a整除,其中63也可以被a整除,所以35也可以被a整除;

    因此这个问题转化为求6335的最大公因数a;

    同理可得

    求(63-35)=2835的最大公因数a;
    求(35-28)=728的最大公因数a;

    70的最大公因数a;
    输出第一个数字;

    这就是更相减损术的原理。
    由此我们可以发现求28和7的最大公因数,一直减7,减到不能减为止。而这个不断减7的过程就是除7取余数,所以可以将其优化为辗转相除法。

    C语言代码实现如下:

    #include<stdio.h>
    int gcd(int a,int b){
    	int temp;
    	while(b!=0){
    		temp=a%b;
    		a=b;
    		b=temp;
    	}
    	return a;
    }
    int main(){
    	int m,n;
    	scanf("%d%d",&m,&n);
    	printf("%d",gcd(m,n));
    	return 0;	
    }
    
    展开全文
  • 辗转相除法 求最大公约数 初中数学知识,快忘了的回顾一下。 假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法,是这样进行的: 1997 / 615 = 3 (余 152) 615 / 152 = 4(余7) 152 / 7 = 21(余5) 7 / ...

    辗转相除法 求最大公约数

    初中数学知识,快忘了的回顾一下。

    假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法,是这样进行的:
    1997 / 615 = 3 (余 152)
    615 / 152 = 4(余7)
    152 / 7 = 21(余5)
    7 / 5 = 1 (余2)
    5 / 2 = 2 (余1)
    2 / 1 = 2 (余0)
    至此,最大公约数为1

    思路: gcd( a , b ) = gcd( b , a%b ) ,其中 gcd 表示 a 和 b 的最大公约数;

    代码1:

    # python 
    m = max(num1, num2)
    n = min(num1, num2)
    r = m % n
    while r != 0:
        m = n
        n = r
        r = m % n
    return n
           
    

    代码:

    def gcd(m,n):
    	return gcd(n,m%n) if n else m #三目运算符,条件运算符
    print(gcd(15,25))
    # 输出5      
    

    时间复杂度:

    两次操作后数据量最差变为原来的一半
    时间复杂度 O(logN)

    展开全文
  • c语言 辗转相除法求最大公约数

    万次阅读 多人点赞 2016-09-22 21:34:22
    用C语言编写辗转相除法求最大公约数

    #include<stdio.h>

    int main()
    {
    int a,b;
    int temp;
    int r = 1;            //一定要初始化

    scanf("%d %d",&a,&b);

    if(a<b)                        //保证除数为最大数
    {
    temp = a;
    a = b;
    b = temp;
    }

    while(r != 0)
    {
    r = a % b;
    a = b;
    b = r;
    }

    printf("%d\n",a);

    return 0;
    }


    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,333
精华内容 5,733
关键字:

辗转相除法求最大公约数