(JAVA)백준 온라인 2609번 - 최대공약수와 최소공배수

나는 바보다

유클리드 최대공약수 알고리즘을 배웠음에도 불구하고 그새 까먹고 이 기본적인 문제도 풀지 못했기 때문이다

여기서 유클리드 최대공약수 알고리즘을 알려주겠다

// for문 사용 유클리드 알고리즘
int gcd(int a, int b){

    while(b!=0){
    	int tmp = a%b;
        a = b;
        b = tmp;
    }
    return a;
}

//재귀 사용
int gcd (int a, int b){
	if(a != 0){
		return gcd(b, a%b);
    }else{
    	return a;
    }
}

이게 바로 최대 공약수를 구하는 유클리드 알고리즘이다!

그리고

최소 공배수를 구하는 방법은

두 수를 곱하고 난 뒤 두 수의 최대 공약수로 나눠주면 된다!

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int d = gcd(a, b); //최대 공약수
        System.out.println(d);
        System.out.println(a*b/d);

        }

        public static int gcd(int a, int b){
            while(b!=0){
                int tmp = a%b; // 나머지 구하기
                a = b;
                b = tmp;
            }
            return a;
        }
}

정답 코드이다 나는 유클리드 반복문에서도 반복문을 사용하였다