최대공약수, 최소공배수

이번엔 할때마다 헷갈렸던 최대공약수와 최소공배수에 대해서 찐막 정리를 해보려고 한다.

그동안 나는 최소공배수를 구하는 문제가 나오면,

1.최대공약수를 구한다.----->2.A*B/최대공약수를 한다.----->3.최소공배수 쨘!!

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

하는 생각으로 코드를 짰다.

백준 13241번

 

package math2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Q2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        long A = Long.parseLong(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        if (A <= B) {
            if (B % A == 0) {
                sb.append(B).append("\n");
            } else {
                for (long j = A-1; j >= 1; j--) {
                    if (A % j == 0 && B % j == 0) {
                        sb.append(A * B / j).append("\n");
                        break;
                    }
                }
            }
        } else {
            if (A % B == 0) {
                sb.append(A).append("\n");
            } else {
                for (long j = B - 1; j >= 1; j--) {
                    if (A % j == 0 && B % j == 0) {
                        sb.append(A * B / j).append("\n");
                        break;
                    }
                }
            }
        }
        System.out.println(sb);
    }
}

 

나의 코드는, 1. A와 B의 대소관계 비교----->2. A로 바로나누어지는지, 나누어지면 최소공배수는 묻따말 B------>

3. "최대"공약수이므로 A-1부터 1까지 줄어들면서 A와B를 나누어주고 동시에 나누어지는 순간, Break!

라고 아주 하드하게 짠것 같다. 하지만 이를 구원해줄 끝냐주는것, 유클리드 호재법을 알게 되었다.

---

https://st-lab.tistory.com/154#algorithm

[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]

압도적 감사를 표합니다.

gcd는 최대공약수이다.

gcd(A,B)==gcd(B,r)
지리는 공식이다.

재귀함수를 써서 r에 0이 들어가면 return B를 해준다. 유클리드 형 이런걸 어케 했냐구용,,,

gcd

앞으로 절대 잊지말자.

잊어버리면 난 침팬지다

우끼끼