개발 지식/알고리즘

[백준] 2609 최대공약수와 최소공배수

트리맨스 2019. 3. 24. 12:21
반응형

문제 : 두 개의 자연수를 입력받아 최대공약수와 최소공배수를 출력하는 프로그램을 작성하시오.


최대공약수와 최소공배수를 출력하는 문제입니다.

최대공약수의 정의는 두 수를 나누어 나머지가 0이 되게 하는 수 중 가장 큰 수이고,

최소공배수는 두 수의 공통의 배수 중 가장 작은 수를 의미합니다.


저는 유클리드 호제법이라는 알고리즘을 사용할 것 입니다.

예를 들어 12와 40의 최대공약수를 구한다면,


40%12=4  //피연산자와 나머지를 

12%4=0   //연산자와 피연산자로 이동해줍니다. 그리고 0이 될때까지 이 과정을 반복합니다.



나머지가 0이 될 때, 그 때의 피연산자가 최대공약수 입니다.

그럼 최소공배수는 어떻게 구할까요? 간단합니다. 두 수의 곱/최대공약수 입니다.


이걸 이용하면 계산을 반복할 필요도 없고 연산 시간도 줄어듭니다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>  /* 유클리드 호제법 알고리즘 사용*/  
 
int main()
{
    int num,k,j=0
    int arr[100000];    
    
 
    scanf("%d %d",&arr[0],&arr[1]);
    if(arr[0]<arr[1])   //맨 왼쪽에 더 큰 수 입력   
    {
        k=arr[1]; arr[1]=arr[0]; arr[0]=k;
    }
    while(1)  //오른쪽으로 가면서 나머지 입력  
    {
        arr[j+2]=arr[j]%arr[j+1]; 
        if(arr[j+2]==0)
        {
            break;
        }
        j++
    }
    printf("%d\n%d",arr[j+1],arr[0]*(arr[1]/arr[j+1]));     
}
cs


반응형

'개발 지식 > 알고리즘' 카테고리의 다른 글

[백준] 14786 Ax+Bsin(x)=C (2)  (8) 2019.05.24
[백준] 1010 다리 놓기  (0) 2019.05.08
[백준] 1929 소수 구하기  (0) 2019.03.19
[백준] 10250 ACM 호텔  (0) 2019.03.15
[백준] 1834 나머지와 몫이 같은 수  (0) 2019.02.27