[백준 / C언어] Day34. 최대공약수와 최소공배수 (2609)

2024. 07. 07 - 코딩테스트 스터디 Day34

 

 

01. 문제

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

 

 

02. 입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000 이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

 

 

03. 출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

 

04-1. 예제 입력 1

24 18

 

 

04-2. 예제 출력 1

6
72

 

 

05-1. 풀이 및 답

#include <stdio.h>

int main() {
    int a, b;
    int gcd = 1;    // 최대공약수
    
    scanf("%d %d", &a, &b);
    
    if (a > b) {
        int tmp = a;
        a = b;
        b = tmp;
    }
    
    for (int i = 2; i <= a; i++) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
        }
    }
    
    printf("%d\n", gcd);
    printf("%d\n", a * b / gcd);
    
    return 0;
}

계산한 최대공약수를 저장할 변수 gcd를 선언한 뒤 1로 초기화해준다.

두 수 a, b를 입력받은 뒤, 두 수의 크기를 비교하여 둘 중 더 작은 수를 a, 더 큰 수를 b로 둔다.

 

i가 2부터 a가 될 때까지 반복문을 돌면서 a와 b를 동시에 나누어 떨어지게 할 수 있는 i값을 찾아 gcd 변수에 갱신해 준다.

반복문을 빠져나왔을 때 gcd에 저장되어 있는 값이 최대공약수이다.

 

최소공약수는 두 수의 곱을 최대공약수로 나누어주면 쉽게 계산할 수 있다.

 

    for (int i = 2; i < a; i++) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
        }
    }

아무 생각 없이 반복문의 범위를 위와 같이 설정해서 한 번 틀렸다

꼭 i가 a일 때의 경우도 계산해봐야 한다는 점을 잊지 말자 ^_^ 

 

정답!

 

---

최대공약수, 최소공배수 너무 오랜만이라 로딩 시간이 조금 걸렸다 크크...