[BaekJoon] 21919 - 소수 최소 공배수

소수 최소 공배수

문제

행복이는 길이가 $N$인 수열 $A$에서 소수들을 골라 최소공배수를 구해보려고 한다.

행복이를 도와 이를 계산해주자.

입력

첫째 줄에 수열 $A$의 길이 $N$이 주어진다. $(1 \le N \le 10,000)$

그 다음줄에는 수열 $A$의 원소 $A_{i}$

답이 263 미만인 입력만 주어진다.

출력

첫째 줄에 소수들의 최소공배수를 출력한다.

만약 소수가 없는 경우는 -1을 출력한다.

예제 입력

5
2 3 5 6 8

예제 출력

30

수열 중에 소수는 2, 3, 5가 있다.

예제 코드

import java.util.Scanner;

public class Main {
    public static boolean sosu(long arr) {
        for (int i = 2; i < Math.sqrt(arr); i++) {
            if (arr % i == 0) {
                return false;
            }
        }
        return true;
    }

    // 최대 공약수
    public static long gcd(long x, long y) {
        while (y != 0) {
            long temp = x % y;
            x = y;
            y = temp;
        }
        return x;
    }

    // 최소 공배수
    public static long lcm(long x, long y) {
        return x / gcd(x, y) * y;
    }

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

        int n = sc.nextInt();
        long ans = 1;

        for (int i = 0; i < n; i++) {
            long a = sc.nextInt();
            if (sosu(a)) {
                ans = lcm(ans, a);
            }
        }

        if (ans == 1) System.out.println(-1);
        else System.out.println(ans);
    }
}