精华内容
下载资源
问答
  • 使用辗转相除法求最大公约数最小公倍数
    // 辗转相除 取最大公约数
        int a = 0;
        int b = 0;
        printf("Enter Two Number:");
        scanf("%d%d",&a,&b);
    
        int multiply = a * b;
        int temp = a % b ;
        while (temp != 0) {
            a  = b;
            b = temp;
            temp = a % b;
        }
        printf("最大公约数是:%d\n",b);
     
        printf("最小公倍数是:%d\n", multiply / b);

    展开全文
  • C语言求最大公约数最小公倍数 1. 最大公约数 1.1 定义 ​ 最大公约数(Greatest Common Divisor,GCD),也称最大公因数、最大公因子,是一种数学概念,指两个或多个整数共有约数中最大的一个。 1.2 解法一:常规...

    C语言求最大公约数及最小公倍数

    1. 最大公约数

    1.1 定义

    ​ 最大公约数(Greatest Common Divisor,GCD),也称最大公因数、最大公因子,是一种数学概念,指两个或多个整数共有约数中最大的一个。

    1.2 解法一:常规法(暴力法)

    1.2.1 定义

    由于最大公约数的本质是一个最大的能同时被两整数整除的自然数。所以我们先比较两数大小,从较大数开始向上递增,直到找到那个最小公倍数。

    1.2.2 代码实现

    int gcd4(int a, int b)
    {
        //首先找到两个数中较大的数,用a存储较大数
        if (a < b)
        {
            int temp = a;
            a = b;
            b = temp;
        }
        //从较大数开始寻找符合条件的最大公约数
        for (int i = a; i > 0; --i)
        {
            if (a % i == 0 && b % i == 0)
            {
                return i;
            }
        }
    }
    

    1.3 解法二:辗转相除法(欧几里德法)

    1.3.1方法解释:

    用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。

    1.3.2实例:

    例如,求(319,377):

    ∵ 319÷377=0(余319)

    ∴(319,377)=(377,319);

    ∵ 377÷319=1(余58)

    ∴(377,319)=(319,58);

    ∵ 319÷58=5(余29)

    ∴ (319,58)=(58,29);

    ∵ 58÷29=2(余0)

    ∴ (58,29)= 29;

    ∴ (319,377)=29。

    1.3.3 代码实现

    /**
     * 递归版辗转相除法
     * @param a
     * @param b
     * @return
     */
    int gcd1(int a, int b)
    {
        if (a % b == 0)
        {
            return b;
        }
        else
        {
            return gcd1(b, a % b);
        }
    }
    
    /**
     * 非递归辗转相除法求解最大公约数
     * @param a
     * @param b
     * @return
     */
    int gcd2(int a, int b)
    {
        while (b != 0)
        {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }
    

    1.4 解法二:更相减损法

    1.4.1 方法解释:

    (如果需要对分数进行约分,那么)可以折半的话,就折半(也就是用2来约分)。如果不可以折半的话,那么就比较分母和分子的大小,用大数减去小数,互相减来减去,一直到减数与差相等为止,用这个相等的数字来约分,这个数就是最大公约数;

    1.4.2 步骤:

    • 第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。

    • 第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。

    • 则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。

    1.4.3 实例:

    1. 用更相减损术求98与63的最大公约数。

    解:由于63不是偶数,把98和63以大数减小数,并辗转相减:

    98-63=35

    63-35=28

    35-28=7

    28-7=21

    21-7=14

    14-7=7

    所以,98和63的最大公约数等于7。

    1. 用更相减损术求260和104的最大公约数。

    解:由于260和104均为偶数,首先用2约简得到130和52,再用2约简得到65和26。

    此时65是奇数而26不是奇数,故把65和26辗转相减:

    65-26=39

    39-26=13

    26-13=13

    所以,260与104的最大公约数等于13乘以第一步中约掉的两个2,即1322=52。

    1.4.4 代码实现

    //定义静态变量,保存约掉的若干个2次数
    static int count = 0;
    
    int gcd3(int a, int b)
    {
        int temp;
        //任意给定两个正整数;判断它们是否都是偶数。
        if (a % 2 == 0 && b % 2 == 0 && !count)
        {
            //若是,则用2约简;若不是则执行第二步。
            a /= 2;
            b /= 2;
            //保存约掉的若干个2次数
            count += 2;
        }
        //以较大的数减较小的数,a中保存大数
        if (a < b)
        {
            temp = a;
            a = b;
            b = temp;
        }
        //接着把所得的差与较小的数比较,并以大数减小数
        if (a - b != 0)
        {
            //递归求解
            return gcd3(b, a - b);
        }
        else
        {
            //计算完毕完后count要置为0,防止第二次调用时出错;
            //所以需要提前定义常量保存输出结果:约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。
            int result = count * b;
            //置0
            count = 0;
            return result;
        }
    }
    

    2. 最小公倍数

    2.1 定义

    最小公倍数(Least Common Multiple(LCM))是一种数学概念,几个数共有的倍数叫做这几个数的公倍数,其中除0以外最小的一个公倍数,叫做这几个数的最小公倍数。

    2.2 解法一:常规法(暴力法)

    2.2.1 方法解释

    由于最小公倍数的本质是一个最小的能同时被两整数整除的自然数。所以我们先比较两数大小,从较大数开始向上递增,直到找到那个最小公倍数。

    2.2.2 代码实现

    /**
     * 常规法求最小公倍数(暴力法)
     * @param a
     * @param b
     * @return
     */
    int lcm1(int a, int b)
    {
        //首先找到两个数中较大的数,用a存储较大数
        if (a < b)
        {
            int temp = a;
            a = b;
            b = temp;
        }
        //从较大数开始寻找符合条件的最小公倍数
        for (int i = a;; ++i)
        {
            if (i % a == 0 && i % b == 0)
            {
                return i;
            }
        }
    }
    

    2.3 解法二:公式法

    2.3.1 定义

    由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。即(a,b)×[a,b]=a×b。所以,求两个数的最小公倍数,就可以先求出它们的最大公约数,然后用上述公式求出它们的最小公倍数。

    2.3.2 实例

    求[18,20],即得[18,20]=18×20÷(18,20)=18×20÷2=180。求几个自然数的最小公倍数,可以先求出其中两个数的最小公倍数,再求这个最小公倍数与第三个数的最小公倍数,依次求下去,直到最后一个为止。最后所得的那个最小公倍数,就是所求的几个数的最小公倍数。

    2.3.3 代码实现

    int lcm2(int a, int b)
    {
        //lcd函数上面已经介绍
        return a*b/lcd(a,b);
    }
    

    约数,然后用上述公式求出它们的最小公倍数。

    2.3.2 实例

    求[18,20],即得[18,20]=18×20÷(18,20)=18×20÷2=180。求几个自然数的最小公倍数,可以先求出其中两个数的最小公倍数,再求这个最小公倍数与第三个数的最小公倍数,依次求下去,直到最后一个为止。最后所得的那个最小公倍数,就是所求的几个数的最小公倍数。

    2.3.3 代码实现

    int lcm2(int a, int b)
    {
        //lcd函数上面已经介绍
        return a*b/lcd(a,b);
    }
    
    展开全文
  • C语言写的,求最大公约数最小公倍数的代码
  • 为了方便学习,这一次我整理了一些用c语言求最大公约数的方法。 #最大公约数? 最大公约数,指两个或多个整数共有约数中最大的一个。 举例说, 能够整除一个整数的整数称为其的约数(如5是10约数); 如果一个数...
    写c语言题目时,我们经常会遇到求最大公约数和最小公倍数的问题。为了方便学习,我整理了一些用c语言求最大公约数的方法。
    

    #最大公约数?
    最大公约数,指两个或多个整数共有约数中最大的一个。
    举例说,
    能够整除一个整数的整数称为其的约数(如5是10约数);
    如果一个数既是数m的约数,又是数n的约数,称为m,n的公约数。m,n的公约数中最大的一个(可以包括m,n自身)称为m,n的最大公约数。

    #更相减损术方法
    利用更相减损术求两个整数的最大公约数,即每次将较大的数变成大数减去小数的值,当满足循环条件(两数相等)输出结果即可。
    举例说,若m=4,n=6,则m!=n且m<n,执行n=n-m->n=2,此时m>n,执行m=m-n->m=2,m=n,输出最大公约数m=2。

    #include<stdio.h>
    int main(){
        int m,n;
        scanf("%d %d",&m,&n);
        while(m!=n){     //相等即得最大公约数
         if(m<n){
            n=n-m;
        }else if(m>n){
            m=m-n;
        }   
    }
        printf("%d",m);
    }
    

    #辗转相除法
    当两个数都较大时,我们一般采用辗转相除法比较方便。
    即以小数除大数,如果能整除,那么小数就是所求的最大公约数;否则就用余数来除刚才的除数;若不能整除,将得到新的余数去除刚才的余数。以此类推,直到一个除法能够整除,这时作为除数的数就是所求的最大公约数。

    #include <stdio.h>
    int main()
    {
    	int m,n,t,a,b;
    	scanf("%d,%d",&m,&n);
    	if(m<n){
          t=m;m=n;n=t;
    	}
    	a=m;
    	b=n;
    	while(b!=0){ /*①a%b得余数c ②若c=0,则b即为两数的最大公约数
    ③若c≠0,则a=b,b=c,再回去执行①*/ 
    	   t=a%b;
    	   a=b;
    	   b=t;	
    	}
    	printf("%d",a);    
    	return 0;
    } 
    

    #穷举法

    #include<stdio.h>
    int main(){
    	int m,n,i,t;
    	scanf("%d %d",&m,&n);
    	if(m<n){
    		t=m;m=n;n=t;
    	}
    	for (i = m; i > 0; i--){
    		if ((m%i == 0) && (n%i == 0)){
    			break;
    		}
    	}
    	printf("%d",i);
    } 
    

    #最小公倍数?
    如果一个数既是a又是b的倍数且这个数在a,b的所有公倍数里为最小,那这个数就是最小公倍数。
    解题重点:最小公倍数=两整数的乘积÷最大公约数

    #include <stdio.h>
    int main()
    {
    	int m,n,t,gys,gbs,a,b;
    	gys=0;gbs=0;
    	scanf("%d,%d",&m,&n);
    	if(m<n)
    	{t=m;m=n;n=t;}
    	a=m;
    	b=n;
    	while(b!=0)    
    	{
    	   t=a%b;
    	   a=b;
    	   b=t;	
    	}
    	printf("gys=%d,gbs=%d",a,m*n/a);   
    	return 0;
    } 
    
    展开全文
  • C语言求最大公约数最小公倍数

    千次阅读 2020-03-22 09:45:34
    问题:请从键盘上输入两个数值 x,y,请用C语言求出这两个数值的最大公约数最小公倍数。 首先,我们要想解决这道问题,就要了解什么是最大公约数最小公倍数。 最大公因数;也称最大公约数、最大公因子,指两个或...

    求最大公约数与最小公倍数

    问题分析

    问题:请从键盘上输入两个数值 x,y,请用C语言求出这两个数值的最大公约数与最小公倍数。

    首先,我们要想解决这道问题,就要了解什么是最大公约数与最小公倍数。

    最大公因数;也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。

    最小公倍数:两个或多个整数公有的倍数叫做它们的公倍数。-

    了解了其含义,接下来就是构思算法,通常而言,求解最大公约数有三种算法,而最小公倍数的求解,我们可以很容易的推断出,最小公倍数等于两个数值的乘积除以这两个数值的最大公约数。那么接下来的算法我将在此一一进行列举和解释。

    1.辗转相除法

    又名欧几里德算法(Euclidean algorithm),它是已知最古老的算法, 其可追溯至公元前300年前。 ----来源百度百科

    辗转:望文生义,就是翻来覆去。相除就很好理解了,就是进行除法运算。

    辗转相除法的核心就是不断的让两个数做除法运算。其原理基于两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。

    假设两数为 x,y。

    先令 z = x % y ;

    之后 y 赋给 x 即令 x = y ;

    再将 z 赋给 y 即令 y = z;

    辗转相减,其终止条件为:y 等于0时。

    代码如下:
    在这里插入图片描述

    辗转相减法

    即尼考曼彻斯法,其特色是做一系列减法,从而求得最大公约数。----来源百度百科

    辗转相减法即通过对两数的不断减法运算。

    假设两数为 x, y。

    当 x > y 时,令 x = x - y;

    反之,则令 y = y - x;

    之后一直辗转相减,直至 x = y 时,终止。

    代码如下:
    在这里插入图片描述

    穷举法

    穷举法的基本思想是根据题目的部分条件确定答案的大致范围,并在此范围内对所有可能的情况逐一验证,直到全部情况验证完毕。----来源百度百科

    穷举法又称枚举法,通过对数值范围内的所有数字进行检验,得出其结果。

    代码如下:
    在这里插入图片描述
    以上即为求解最大公约数与最小公倍数的三种算法

    展开全文
  • 求最大公约数算法: (1)辗转相除法 有两整数a和b: ①a%b得余数c ②若c=0,则b即为两数的最大公约数 ③ 若c≠0,则a=b,b=c,再回去执行① 例如求27和15的最大公约数过程为: 27÷15余1215÷12余312÷3余0...
  • C语言求最大公约数最小公倍数的各种算法的总结,辗转相除法,穷举法等等
  • C语言 | 最大公约数最小公倍数

    千次阅读 2020-12-27 20:50:13
    例45:C语音编程实现求两个数的...最小公倍数=两整数的乘积÷最大公约数 , 所以怎么求最大公约数是关键。 源代码演示: #include<stdio.h>//头文件 int main()//主函数 { int m, n, num1, num2, temp;//定义
  • 1. 输入2个正整数m和n,最大公约数GCD和最小公倍数GCM 公式:最小公倍数GCM=m*n/最大公约数GCD */ int m,n,max,min,swap; printf(“输入两个正整数,用逗号隔开: “); scanf(”%d,%d”,&m,&n); //...
  • 关于如何求最大公约数最小公倍数c语言程序
  • 一、求最大公约数 先分析一个问题:如何求任意两个非负整数的最大公约数(GCD),这里我们不用逐个试的暴力破解,而采用巧妙的欧几里得算法。先看如下证明过程(证明主要摘自百度百科~~): 定理:两个整数的...
  • #include int gcd(int a, int b) {  return !b?a:gcd(b,a%b); //b=0,返回a,b!=0,返回,a和a%b取余的最大公约数  } int lcm(int a, int b)... //a,b得最小公倍数,a乘b除以最大公约数  } int main()

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 792
精华内容 316
关键字:

c语言求最大公约数最小公倍数

c语言 订阅