백준 2609 자바 - 최대공약수와 최소공배수

문제

---

 

 

문제해결

---

- 유클리드 호제법을 이용한다

- gcd(a, b) = gcd(b, r) 이므로 b가 0이 될때까지 gcd 메소드를 실행하면 최대공약수를 구할 수 있다

- a * b / c(최대공약수)를 하면 최소공배수를 구할 수 있다

import java.util.Scanner;
//최대공약수와 최소공배수
public class B2609 {

    //최대공약수 재귀 방식
    public static int gcd(int a, int b){
        if (b==0) return a;
        //gcd(a,b) = gcd(b,r) 이므로 r을 a%b로 바꿔줌
        return gcd(b, a%b);
    }

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

        //최대공약수
        int c = gcd(a, b);

        System.out.println(c);
        System.out.println(a * b / c);//최소공배수
    }
}

출처: https://st-lab.tistory.com/154