[JO] 1658 최대공약수와 최소공배수

1. 문제

JUNGOL

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

---

2. 풀이

a>=b일 때, a%b==0이면 a와 b의 최대공약수는 b다.

a%b!=0이라면 a와 b의 최대공약수는 b와 a%b의 최대공약수와 동일하다.

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

public class JO_1658_최대공약수와최소공배수 {
   public static void main(String[] args) throws IOException {
      StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());
      int A = Integer.parseInt(st.nextToken());
      int B = Integer.parseInt(st.nextToken());
      int g = gcd(A,B);
      System.out.println(g+"\n"+A/g*B);
   }
   private static int gcd(int a, int b){
      if(a<b){
         int tmp = a;
         a = b;
         b = tmp;
      }

      if(a%b==0) return b;
      return gcd(b,a%b);
   }
}

---

3. 결과