如何用C语言求最大公约数-蒲公英云

如何用C语言求最大公约数

た入场券 2022-07-15 05:57 374阅读 0赞

方法一：

辗转相减法：用两个数中较大的数减去较小的数一直减到两个数相等为止

最大公约数M一定能能够被两个数同时整除即a=x*M,b=y*M故两个数相减之后的结果=M*z

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
int MAX(int x, int y)
{
    while (1)
    {
        if (x > y)
        {
            x = x - y;
        }
        if (x < y)
        {
            y = y - x;
        }
        if (x == y)
            return x;
    }
}
int  main()
{
    int a = 0;
    int b = 0;
    int result = 0;
    scanf("%d%d",&a, &b);
    result=MAX(a, b);
    printf("%d", result);
    system("pause");
    return 0;
}

方法二：
辗转相除法求最大公约数:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
int MAX(int x, int y)
{
    while (1)
    {
        if((x>y)&&x!=0&&y!=0)
        {
            x = x%y;
        }
        if((y>x)&&x!=0&&y!=0)
        {
            y = y %x;
        }
        if (x==0)
            return y;
        if (y == 0)
            return x;
    }
}
int  main()
{
    int a = 0;
    int b = 0;
    int result = 0;
    scanf("%d%d",&a, &b);
    result=MAX(a, b);
    printf("%d", result);
    system("pause");
    return 0;
}