D+7 백준 2609 최대공약수와 최소공배수

백준 2609 최대공약수와 최소공배수 - 실버 5

* 손으로 최대공약수와 최소공배수를 구할때를 참고하였다.

2	24	18
3	12	9
	4	3

어렸을 적 최대공약수와 최소공배수를 구할때는 상기 표와 같이 진행했다.

1) 공통의 약수로 나누어 떨어지지 않을 때까지 나눈다. 

2) 최대공약수 : 왼편의 나누는 값의 곱 (2 * 3)

3) 최소공배수 : 왼편의 나누는 값 * 나머지의 값 (2 * 3 * 4 * 3)

이걸 코드로 진행하면 입력받은 두 수를 나누는 나머지가 0인 수를 계속 곱해간다 > 이것이 최대공약수가 된다.

끝까지 가서 나누어 떨어지지 않을때, 남은 숫자들을 다 곱한다 > 최소공배수

 

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

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

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 n1 = Integer.parseInt(st.nextToken());
        int n2 = Integer.parseInt(st.nextToken());
        
        int r1 = 1, r2 =1; // r1 최대공약수, r2 최소공배수
        
        int num1= n1, num2 = n2; //계산해나갈값
        //boolean flag = false;
        while(true){
            for(int i=2; i<10000 ; i++){
                if(num1%i==0 && num2%i==0){ //둘다 나머지가 0으로 나누어떨어질때
                    r1 *=i; // 최대공약수 나누는 i값을 계속 곱해간다.
                    num1 = num1/i;
                    num2 = num2/i; //수가 변한다.
                    break;
                }
                if(i==9999){ //안나누어지고 끝까지 왔으면 최소공배수 구함
                    r2 = r1*num1*num2; //최소공배수 = 최대공약수 * 남게되는 숫자 값들.
                    System.out.println(r1);
                    System.out.println(r2);
                    return;
                    //flag = true;
                }
            }
        }
        
    
    }//main method end
}//class end