[기본 알고리즘] 최대공약수(GCD), 최소공배수(LCM) 구하기

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

2609번: 최대공약수와 최소공배수

문제풀이

최대공약수(GCD) - Greatest Common Divisor

두 자연수가 갖는 약수 중, 공통된 가장 큰 약수를 말한다.

 

최소공배수(LCM) - Least Common Multiple

두 자연수의 배수들 중, 공통된 가장 작은수를 말한다.

최소 공배수 = 두 자연수의 곱 / 최대 공약수

 

문제풀이1)

#include <iostream>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n;
    cin >> m;

    int answer1, answer2;
    for (int i = 1; i <= n; i++)
    {
        if (n % i == 0)
        {
            if (m % i == 0)
            {
                answer1 = i;
            }
        }
    }

    int dd = 1;
    int n2;
    while (1)
    {
        n2 = n * dd;
        if (n2 % m == 0)
        {
            answer2 = n2;
            break;
        }

        dd += 1;
    }

    cout << answer1 << "\n";
    cout << answer2 << "\n";

    // return 최대공약수 최소공배수
    // return answer1 answer2
}

 

 

문제풀이2) (최소 공배수 = 두 자연수의 곱 / 최대 공약수 공식을 이용)

#include <iostream>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n;
    cin >> m;

    int answer1, answer2;
    for (int i = 1; i <= n; i++)
    {
        if (n % i == 0)
        {
            if (m % i == 0)
            {
                answer1 = i;
            }
        }
    }

    answer2 = n * m / answer1;

    cout << answer1 << "\n";
    cout << answer2 << "\n";

    // return 최대공약수 최소공배수
}