[CodingTest] 최대 공약수, 최소 공배수, 소인수

 

📝 

 

최대 공약수 (GCD, Greatest Common Divisor)

두 수의 공통된 약수 중 가장 큰 값을 최대 공약수라 한다.

//재귀 방식 활용
public static int getGCD(int a, int b) {
	if (b == 0) return a;
    return getGCD(b, a % b);
}

 

 

최소 공배수 (LCM, Least Common Multiple)

두 수의 공통된 배수 중 가장 작은 값을 최소 공배수라 한다.

public static int getLCM(int a, int b) {
	return (a * b) / getGCD(a,b);
}

 

소인수

어떤 수를 소수들의 곱으로 표현할 수 있다면, 그 소수들을 소인수라 한다.

 

1) 소수인지 확인

private boolean isPrime(int n) {
    for (int i = 2; i <= n / 2; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

 

2) 소인수 구하기

public Set<Integer> primeFactors(int n) {
    Set<Integer> result = new HashSet<>();
    for (int i = 2; i <= n; i++) {
        while (n % i == 0) {
            result.add(i);
            n /= i;
        }
    }
    return result;
}