백준 2909 최대공약수와 최소공배수 | 자바 java

 

이번 포스팅은 백준 2609번 최대공약수와 최소공배입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

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

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

 

 

 

기본 알고리즘

• 수학
• 정수론
• 유클리드 호제법

 

반응형

 

전체 코드

 

import java.util.Scanner;
 
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num1=0, num2=0, gcd=0, lcm=0;
 
        num1 = sc.nextInt();
        num2 = sc.nextInt();
 
        if(num1<num2){
            int tmp = num1;
            num1=num2;
            num2=tmp;
        }
 
        //최대공약수
        for(int i=1; i<=num1; i++){
            if(num1%i==0 && num2%i==0){
                gcd=i;
            }
        }
 
        //최소공배수
        for(int j=num2; j<=num1*num2; j++){
            if(j%num1==0 && j%num2==0){
                lcm=j;
                break;
            }
        }
 
        System.out.println(gcd);
        System.out.println(lcm);
 
        sc.close();
    }
}