辗转相除法求最大公约数和最小公倍数

辗转相除法求最大公约数和最小公倍数,第1张

辗转相除法求最大公约数最小公倍数

辗转相除法,欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。

算法思路:先找出俩个数最大的数a,用最大的数对小的数b取余,a%b若余数r不为0,则将除数作为新的被除数,余数给新除数。循环直到余数r为0,则最后一次运算的除数则为最大公约数。

 

假如需要求 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

 

流程图如下:

 

 算法实现

C实现:

#include
int main()
{
    int a,b,t,r,n;
    printf("请输入俩个数 a bn");
    scanf("%d %d",&a,&b);
    if(ab,将a,b 交换位置, 将大的放在前面,换位置之后a=16,b=12。 
    {t=b;b=a;a=t;}
    r=a%b;  //这里的余数为4。 
    n=a*b;  //n=12*16 
    while(r!=0)   //第一次r=4,不等于0,进入 
    {
        a=b;  //第一次 a=b=12.
        b=r;  //第一次 b=4.
        r=a%b;//第一次 r=0; 则不会进入下一次   最小公倍数就是b 
    }
    printf("最大公约数是%d,最小公倍数是%dn",b,n/b);
    
    return 0;
}

java实现

import java.util.Scanner;

public class TossAndTurnAndDivide {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.println("请输入俩个数");
        int a = in.nextInt();
        int b = in.nextInt();
        int t,r,n;
        if(a 

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/zaji/5671570.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-16
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表(0条)

保存