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

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

程序分析:
(1)最小公倍数=输入的两个数之积除于它们的最大公约数,关键是求出最大公约数;
(2)求最大公约数用辗转相除法(又名欧几里德算法)

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

#include<stdio.h>

int main()
{
    int a,b,c;
    int raw_a,raw_b;
    scanf("%d %d",&a,&b);
    raw_a=a;raw_b=b;
    c=a%b;
    while (c!=0)
    {
        a=b;b=c;
        c=a%b;
    }
    printf("a与b的最大公约数是:%d\n",b);
    printf("a与b的最小公倍数是:%d\n",raw_a*raw_b/b);
    return 0;
}
12 56
a与b的最大公约数是:4
a与b的最小公倍数是:168

具体步骤:

#include<stdio.h>

int main()
{
    int a,b,c;
    int raw_a,raw_b;
    scanf("%d %d",&a,&b);
    raw_a=a;raw_b=b;
    c=a%b;
    printf("%d = %d * %d + %d\n",a,a/b,b,a%b);
    while (c!=0)
    {
        a=b;b=c;
        c=a%b;
        printf("%d = %d * %d + %d\n",a,a/b,b,a%b);
    }
    printf("\n");
    printf("a与b的最大公约数是:%d\n",b);
    printf("a与b的最小公倍数是:%d\n",raw_a*raw_b/b);
    return 0;
}
789 456
789 = 1 * 456 + 333
456 = 1 * 333 + 123
333 = 2 * 123 + 87
123 = 1 * 87 + 36
87 = 2 * 36 + 15
36 = 2 * 15 + 6
15 = 2 * 6 + 3
6 = 2 * 3 + 0

a与b的最大公约数是:3
a与b的最小公倍数是:119928
1221 451
1221 = 2 * 451 + 319
451 = 1 * 319 + 132
319 = 2 * 132 + 55
132 = 2 * 55 + 22
55 = 2 * 22 + 11
22 = 2 * 11 + 0

a与b的最大公约数是:11
a与b的最小公倍数是:50061
上一篇:P1029 最大公约数和最小公倍数问题


下一篇:批处理命令如何输出保持三位的数字,不足补0