백준 최대공약수와 최소공배수(2609) java

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1

24 18

예제 출력 1

6
72

try1

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String args[]) throws IOException {

         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(br.readLine(), " ");

         int N = Integer.parseInt(st.nextToken());
         int K = Integer.parseInt(st.nextToken());
         int CDGYS = 1;
         int CDGBS = 1;

         for(int i = N; i >= 1; i--){
            if(N % i == 0){
                if(K % i == 0){
                    CDGYS = i;
                    break;
                }
            }
         }
         
         CDGBS = CDGYS * (N / CDGYS) * (K / CDGYS);
         System.out.println(CDGYS);
         System.out.println(CDGBS);
    }
}

🔖 Notes

• 문제의 흐름
  • 처음에 약수 구하기를 했었던 과거의 알고리즘 풀이를 기억 못함 → 약수구하기부터 헤맴
  • 약수를 전부 구해서 배열 비교해서 최대공약수 최소공배수를 구하려는 미친 생각을 함
  • 약수구하기가 기적적으로 기억나면서 최대공배수는 가볍게 풀었음~