(기초 알고리즘) 최대공약수 구하기: 유클리드 호제법

#C언어 #재귀호출 #최대공약수 #유클리드호제법

 

 

C언어: 유클리드 호제법을 이용한 최대공약수 구하기

1.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
    int a,b, m,n;

    printf("두 정수 입력: ");
    scanf("%d %d",&a,&b);

    m=a; n=b;
    while (m!=n){
        if (m>n)
            m=m-n;
        else
            n=n-m;
    }
    printf("%d, %d의 최대공약수 = %d\n",a, b, m);

    return 0;
}

 

 

2.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int gcd(int a, int b)
{
    int c;
    while (b)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}
int main()
{
    int a, b;

    printf("두 정수 입력: ");
    scanf("%d %d", &a, &b);

    printf("%d, %d의 최대공약수 = %d\n", a, b, gcd(a,b));

    return 0;
}

 

3. 재귀호출 이용

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int a, b;

    printf("두 정수 입력: ");
    scanf("%d %d", &a, &b);

    printf("%d, %d의 최대공약수 = %d\n", a, b, gcd(a,b));

    return 0;
}