본문 바로가기
Algorithm/알고리즘 설명

[알고리즘] 최대공약수, 최소공배수 구하기

by Sky Titan 2020. 8. 22.
728x90
import java.util.*;

public class Main {


    public static void main(String[] args) {

        int a = 8;
        int b = 6;


        //최대공약수 (유클리드호제법)
        System.out.println("최대공약수 : "+gcd(a,b));

        //최소공배수 = 0이 아닌 두 수의 곱 / 최대공약수
        System.out.println("최소공배수 : "+ (a * b) / gcd(a,b));
    }

    //최대공약수
    public static int gcd(int a, int b)
    {
        //a에 큰 값 위치 시킴
        if(a < b)
        {
            int temp = a;
            a = b;
            b = temp;
        }

        //유클리드 호제법
        while(b != 0)
        {
            int n = a % b;
            a = b;
            b = n;
        }

        //b가 0이 되는 순간, a가 두 수의 최대공약수
        return a;
    }
}

최대공약수 (유클리드 호제법)

  1. ​a, b 중 a에 더 큰 값을 위치 시킨다.
  2. b가 0이 될 때까지 a%b를 반복
  3. a = b 대입
  4. b = a%b의 결과 대입
  5. b = 0이 될 때, a 값 = 최대공약수

최소공배수

최소공배수 = 0이 아닌 두 수의 곱 / 최대공약수

728x90

댓글