[백준 자바] 21919번(소수 최소 공배수)

난이도 - 실버 3

문제

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

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

입력

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

그 다음줄에는 수열 𝐴$A$의 원소 𝐴𝑖$A_{i}$가 공백으로 구분되어 주어진다. (2≤𝐴𝑖≤1,000,000)$(2 \le A_{i} \le 1,000,000)$ 

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

출력

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

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

 

---

 

728x90

수열에 중복되는 소수가 있을 수 있으므로 입력값들을 set에 저장한다. 입력값들 중 가장 큰 수만큼의 소수 배열을 생성하여 set의 원소가 소수면 곱하기를 반복한다.

import java.io.*;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main21919 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    Set<Integer> inputs = new HashSet<>();
    int max = 0;

    for (int i = 0; i < N; i++) {
      int input = Integer.parseInt(st.nextToken());
      inputs.add(input);
      max = Math.max(max, input);
    }

    boolean[] isPrime = sieveOfEratosthenes(max);
    long result = 1;

    for (int i : inputs) {
      if (!isPrime[i])
        result *= i;
    }

    if (result == 1)
      bw.write("-1");
    else
      bw.write(String.valueOf(result));

    bw.flush();
    br.close();
    bw.close();
  }

  static boolean[] sieveOfEratosthenes(int max) {
    boolean[] isPrime = new boolean[max + 1];

    for (int i = 2; i * i <= max; i++)
      if (!isPrime[i])
        for (int j = i * i; j <= max; j += i)
          isPrime[j] = true;

    return isPrime;
  }
}