(자바 코테연습) 최대공약수와 최고 공배수

 

 

Java 코드 예제

문제 설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3,12)는 [3,12]를 반환해야 합니다.

 

제한사항

-두 수 는 1이상 10000000이하의 자연수입니다.

 

 

        import java.util.ArrayList;

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        
        // 최대공약수(GCD) 구하기
        int gcd = gcd(n, m);
        answer[0] = gcd;
        
        // 최소공배수(LCM) 구하기
        int lcm = (n * m) / gcd;
        answer[1] = lcm;
        
        // 소수 찾기
        ArrayList primes = findPrimes(lcm);
        // primes 리스트는 2부터 lcm 미만의 소수를 담고 있음
        
        // 예시로 답을 출력하고 있으므로, 실제 문제에 맞는 출력 방식으로 수정 필요
        
        return answer;
    }
    
    // 최대공약수(GCD)를 구하는 메서드 (유클리드 호제법)
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return Math.abs(a); // 절댓값 처리
    }
    
    // 주어진 수까지의 소수를 찾는 메서드
    private ArrayList findPrimes(int limit) {
        ArrayList primes = new ArrayList<>();
        
        for (int num = 2; num < limit; num++) {
            boolean isPrime = true;
            for (int i = 2; i <= Math.sqrt(num); i++) {
                if (num % i == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                primes.add(num);
            }
        }
        
        return primes;
    }
}