최대공약수, 최소공배수 > 문제은행

본문 바로가기


실력키우기 수학

1002 : 최대공약수, 최소공배수

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 1732 회    시도횟수: 5084 회   



n개의 정수를 입력받아서 최대공약수와 최소공배수를 구하는 프로그램을 작성하여 보자.


첫째 줄에 N (2≤N≤10) 을 입력받고 다음 줄에 N개의 정수를 공백으로 구분하여 입력받는다.
입력받는 정수는 2이상 10 000 이하이다.데이터의 크기가 주어진 범위를 벗어나는 입력은 없다.


입력받은 정수들의 최대공약수와 최소공배수를 공백으로 구분하여 출력한다.최소공배수는 20억 이하의 정수이다.

[Copy]
3
2 8 10
[Copy]
2 40


두 개의 수 A와 B의 최대공약수를 D라 하면, 세 개의 수 A, B, C의 최대공약수는 D와 C의 최대공약수와 같다. 이런 규칙을 이용하면 두 수의 최대공약수를 
구하는 함수 한 개만으로도 여러 수의 최대공약수를 구할 수 있다. 
최소공배수 역시 두 수의 최소공배수를 구해 나가는 방법으로 구할 수 있다. 
a배열에 N개의 수가 저장되어 있다고 가정한다면 다음과 같이 구현할 수 있다.

코드
01    gcd = lcm = a[0];
02    for (i=1; i < N; i++) {
03        gcd = gcd_get(gcd, a[i]);
04        lcm = lcm * a[i] / gcd_get(lcm, a[i]);
05    }

코드분석
첫 번째 수를 최대공약수(gcd)로 정하고 두 번째 수부터 이전까지의 최대공약수(gcd)와 현재 배열의 값(a[i])의 최대공약수를 구하여 다시 gcd에 저장한다. 
이러한 작업을 마지막까지 반복하면 모든 수의 최대공약수가 구해진다.
최소공배수도 같은 방법으로 구할 수 있다.



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.