BOJ 2609. 최대공약수와 최소공배수

BOJ 2609. 최대공약수와 최소공배수

풀이

최대 공약수를 구하는 방법 1

int getGCP(int a, int b) {
    int r = 1;
    for (int i = 2; i < Math.min(a, b); i++) {
        if (a % i == 0 && b % i == 0) {
            r = i;
        }
    }
    return r;
}

2부터 a와 b 중 작은 값 까지
a와 b 모두 나머지가 0인 수를 찾기

최대 공약수를 구하는 방법 2

유클리드 호제법을 재귀 함수를 통해 구현

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

최대 공약수를 구하는 방법 3

유클리드 호제법 while문 사용하여 구현

  int getGCP(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }

java

import java.io.*;
import java.util.Scanner;

class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        int gcp = getGCP(a, b);
        int lcm = getLCM(a, b, gcp);

        System.out.println(gcp);
        System.out.println(lcm);
        sc.close();
    }

    static int getGCP(int a, int b) {
        int r = 1;
        for (int i = 2; i < Math.min(a, b); i++) {
            if (a % i == 0 && b % i == 0) {
                r = i;
            }
        }
        return r;
    }

    static int getLCM(int a, int b, int gcp) {
        return a * b / gcp;
    }
}

kotlin

import java.util.*

fun getGCP(a: Int, b: Int): Int = if (b == 0) a else getGCP(b, a % b)
fun getLCM(a: Int, b: Int): Int = a * b / getGCP(a, b)

fun main() {
    val sc = Scanner(System.`in`)
    val a = sc.nextInt()
    val b = sc.nextInt()

    val gcp = getGCP(a, b)
    val lcm = getLCM(a, b)

    println(gcp)
    println(lcm)
}

소스풀이

github.com/beomjo/algorithm-study/blob/main/BOJ/java/2609.java github.com/beomjo/algorithm-study/blob/main/BOJ/kotlin/2609.kt