최대공약수, 최소공배수

유클리드 호제법

최대공약수(a, b) = 최대공약수(b, r)
r = a와 b를 나눈 나머지 (단, a > b)

#while문 사용

 int gcd(int a, int b) { 
    while(b!=0) {
      int r=a%b;
      a=b;
      b=r;
    }
    return a;
  }

#재귀함수 사용

int gcd(int a, int b) { 
		if(a%b ==0) {
			return b;
		}
		return gcd(b, a%b);
	}

최소공배수
ab = 최대공약수x최소공배수 이므로
최소공배수 = a*b/gcd

int lcm(int a, int b) { 
		return a*b / gcd(a,b);
	}