(2) [C++, Java] 백준 No.2609 : 최대공약수와 최소공배수

문제

풀이

자세한 풀이 : 

 

- 최소공배수를 구할 때 A, B는 10,000 이하의 수 라고 하였으므로, 둘 다 최대로 10,000 일 때 A x B = 100,000,000 (1억) 이므로  
   int형의 저장범위를 벗어나지 않기 때문에 자료형은 크게 신경쓰지 않아도 된다.

 

# C++

#include <iostream>

using namespace std;

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

int main()
{
    int a, b;
    cin >> a >> b;

    int gcd = getGCD(a, b); // 최대공약수 : 유클리드 호제법 사용
    int lcm = a*b/gcd;      // 최소공배수 : gcd x lcm = A x B 이용

    cout << gcd << endl;
    cout << lcm << endl;
}

# Java

import java.util.*;

public class Main {
    public static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x%y);
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int g = gcd(a, b);
        int l = a * b / g;
        System.out.println(g);
        System.out.println(l);
    }
}