lcm (1) 썸네일형 리스트형 BOJ 2609 : 최대공약수와 최소공배수 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 풀이 앞의 약수에서 참고한 알고리즘인 '유클리드 호제법'을 조금만 참고하면 된다. 두 수의 최대 공약수는 두 수의 나머지를 계속 나눔으로써, 언젠가 나누어 떨어지는 수를 의미한다. 그리고 최소 공배수는 두 수의 최대 공약수로 구성된 최소의 수 이므로 x(a를 최대공약수로 나눈 수)*y(b를 최대공약수로 나눈 수)*GCD(a,b)로 귀결된다. 이는 두 수(a = x* GCD(a,b), b = y*GCD(a,b))로 구성 되어 있기 때문에 각각의 최소 공배수는 위와 같이 구성된다. 최대공약수(GCD : Greatest Common Divisor) 최소공배수(LCM : Least Common Multiple) impo.. 이전 1 다음