[BOJ_21919] 소수 최소 공배수

설명

---

이제껏 풀었던 기법을 모두 사용했다 (유클리드 호제법 : 최소공배수) lcm = (a*b) / GCD(a,b); 

private static long lcm(long a ,long b) {
    long lcm = 0L;
    for (int i = 0; i < primes.size(); i++) {
        lcm = (a*b) / gcd(a, n);
    }
    return lcm;
}

소수 구하기는 모두 시도 하되 Math.sqrt(n) 만큼 반복문을 돌리기

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

최대공약수 GCD이용 

private static long gcd(long a, long b) {
    if(b == 0)
    {
        return a;
    }
    else{
        return gcd(b,a%b);
    }
}

 

사실 위를 제대로 이해하려면 정수론을 공부해야 한다고 한다만 암호학에 관심을 두지 않고 있기 때문에 해당 공식들을 보고 많이 풀어서 외워서 적용했다.

 

 

코드

---

package Math;
import java.util.*;

public class BOJ_21919 {
    private static long gcd(long a, long b) {
        if(b == 0)
        {
            return a;
        }
        else{
            return gcd(b,a%b);
        }
    }

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

    private static long lcmOfPrimes(List<Long> primes) {
        long lcm = 1L;
        for (int i = 0; i < primes.size(); i++) {
            lcm *= primes.get(i) / gcd(lcm, primes.get(i));
        }
        return lcm;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        long[] A = new long[N];

        // 소수들 저장
        List<Long> primes = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            A[i] = sc.nextLong();

            // 소수일 경우 primes 배열에 추가
            if (isPrime(A[i])) {
                primes.add(A[i]);
            }
        }

        // 소수가 하나도 없으면 -1 출력
        if (primes.size() == 0) {
            System.out.println(-1);
        } else {
            // 소수들의 최소공배수 출력
            System.out.println(lcmOfPrimes(primes));
        }
    }
}

21919번: 소수 최소 공배수