최소공배수와 최대공약수 (C++ 구현소스 포함)
- 최초 등록일
- 2008.12.01
- 최종 저작일
- 2008.10
- 6페이지/
MS 워드
- 가격 1,000원
![할인쿠폰받기](/images/v4/document/ico_det_coupon.gif)
소개글
최소공배수와 최대공약수를 구하는 5가지 방법과 각각의 방법에 대한 C++ 소스코드를 첨부합니다.
목차
개요
방법1. 소인수분해
방법2. Brute Force
방법3. Euclid Algorithm - Using Recursion
방법4. Euclid Algorithm - Using Iteration
방법1. Euclid Algorithm - Original Version
본문내용
최소공배수와 최대공약수를 구하는 방법은 여러가지가 있지만, 여기에서는 다음과 같은 5 가지 방법에 대해서 소개해 본다.
최소공배수(最小公倍數, LCM : least common multiple)는 두 개의 정수에 대해 둘 모두의 배수가 되는 최소의 자연수를 말한다. 둘 중에 하나가 0일 때에 최소공배수는 0으로 한다. 최소공배수는 LCM(least common multiple))이라고 자주 줄여쓰며, 정수 a, b의 최소공배수는 lcm(a, b)로 표기한다. 예를 들면,
lcm(12, 18) = 36
lcm(17, 11) = 187
등이다.
최대공약수(最大公約數)란, 0 이 아닌 두 정수의 공통되는 약수중에서 가장 큰 수를 말한다. 두 정수 a와 b의 최대공약수를 기호로 gcd(a, b)로 표기하거나, 더 간단히 (a, b)로도 표기한다.
만약 두 수의 최대공약수가 1 과 -1 밖에 없다면, 이 두수는 서로소 라고 한다.
한편, 최소공배수와 최대공약수를 구하는 방법은 아래와 같이 여러가지가 존재한다.
아래의 소스 코드들은, 모두 2 개의 수를 입력받아 해당 숫자의 최소공배수와 최대공약수를 출력하는 프로그램이다.
참고 자료
없음