시작하기전에..

결국 펜을 들고 유클리안 호제법을 하나하나 따라가며 이해보았다. 내가 생각했던 case들에 대한 검증이 10분도 채 걸리지 않았다. 답답한 마음이 조금은 풀렸다.

최소공배수

• 최소공배수는 줄여서 LCM이라고 한다.
• 두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수.
• 최소공배수는 GCD를 이용해서 구할 수 있다.
• 두 수 a,b의 최대공약수를 g라고 했을 때,
• 최소공배수 l = g * (a/g) * (b/g) 이다.

예시문제(1)

https://www.acmicpc.net/problem/1934

솔루션

아주 간단한 문제이다.

#include <iostream>

using namespace std;

int GCD(int a, int b){
    if (b == 0){
        return a;
    }
    else {
        return GCD(b, a % b);
    }
}

int LCM(int a, int b){

} 

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n, m;
        cin >> n >> m;

        int g = GCD(n, m);
        
        // 최소 공배수 식.
        int l = g * (n / g) * (m / g);

        cout << l << '\n';
    }
    return 0;
}

예시문제(2)

https://www.acmicpc.net/problem/2609

솔루션

두 수의 최대공약수와 최소공배수를 함께 구하는 문제이다. 크게 어렵지 않았다.

#include <iostream>

using namespace std;

int GCD(int a, int b){
    if (b == 0){
        return a;
    }
    else {
        return GCD(b, a % b);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;

    int g = GCD(n, m);
    
    int l = g * (n / g) * (m / g);

    cout << g << '\n';
    cout << l;

    return 0;
}

모든 문제가 딱히 어렵진 않았지만, 계속 최대공약수, 최소공배수 식을 까먹고 있다.. 나중에 당황하지 않게 머릿속에 꼭 이해하고 있어야겠다..

최대공약수, 최소공배수는 여기서 마무리 하고, 이제 '소수'로 넘어간다.

+ 왜 자꾸 글을 수정했을때 '수정하기' 버튼이 가끔 활성화되지 않을까,, 임시 저장 후 나중에 해봐야겠다.