유클리드 알고리즘(GCD) c++ 코드

유클리드 알고리즘란?

 

- 주어진 두 수 사이에 존재하는 최대 공약수(GCD)를 구하는 알고리즘

 

작동 원리

자연수 x, y 가 주어질때 큰값이 x라고 하면

x를 y로 나눠 나머지가 0이 아니면 x와 y를 바꾼뒤 나머지가 0일때까지 계속 반복

x를 y로 나눈 나머지가 0일때 y가 최대 공약수

두가지 풀이 방법이 있다. 

while 문 이용 하는법 과 재귀 함수 이용하는 방법

문제 예시

16과 12의 최대 공약수를 구하라

풀이 1 : while 문 이용

C++ 소스 코드

#include <iostream>

int gcd(int x, int y){

    int temp;

    if(x<y){

        temp = x;

        x= y;

        y = temp;

    }

    int rest;

    while(y!=0){

        rest = x%y;

        x = y;

        y = rest;

    }

    return x;

}

int main(){

    int x = 16;

    int y = 14;

    int result;

    result = gcd(x,y);

    std::cout << result;

    return 0;

}

풀이 2 : 재귀 함수 이용

C++ 소스 코드

#include <iostream>

int gcd(int x, int y){

    if(y == 0){

        return x;

    } else {

        return gcd(y, x%y);

    }

}

int main(){

    int x = 16;

    int y = 14;

    int result;

    result = gcd(x,y);

    std::cout << result;

    return 0;

}