단계별로 풀어보기(정수론 및 조합론 - 최대공약수와 최소공배수)

2609번: 최대공약수와 최소공배수 (acmicpc.net)

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

http://boj.kr/cc88c84df0de4bb88d1129863af22e3a

공유 소스 보기

import java.util.Scanner;

class Main{
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
		
		int num1,
			num2 = 0,
			multiply,
			store;
		
		num1 = sc.nextInt();
		
		multiply = sc.nextInt();
		
		if(num1 < multiply) {
			
			num2 = num1;
			num1 = multiply;
			
		}else {
			
			num2 = multiply;
			
		}
		
		multiply = num1 * num2;
		
		while(num2 != 0) {
			
			store = num2;
			num2 = num1 % num2;
			num1 = store;
			
		}
		
		System.out.println(num1);
		System.out.println(multiply / num1);
        
    }
    
}

 

for문 이용해서 전체 탐색하려다가

 

유클리드 호제법 이용해서 풀었다.

 

Botherahn :: [대수학 - 정수론] 유클리드 호제법에 대하여 (tistory.com)

[대수학 - 정수론] 유클리드 호제법에 대하여

여기 참고