728x90
난이도 - 실버 3
문제
행복이는 길이가 𝑁 인 수열 𝐴 에서 소수들을 골라 최소공배수를 구해보려고 한다.
행복이를 도와 이를 계산해주자.
입력
첫째 줄에 수열 𝐴 의 길이 𝑁 이 주어진다. (1≤𝑁≤10,000)
그 다음줄에는 수열 𝐴 의 원소 𝐴𝑖 가 공백으로 구분되어 주어진다. (2≤𝐴𝑖≤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;
}
}
728x90
'백준 > Java' 카테고리의 다른 글
[백준 자바] 2312번(수 복원하기) - 소인수분해 (0) | 2024.06.25 |
---|---|
[백준 풀이] 1747번(소수&팰린드롬) (0) | 2024.06.25 |
[백준 자바] 7789번(텔레프라임) - 소수 판정 (0) | 2024.06.24 |
[백준 자바] 1644번(소수의 연속합) (0) | 2024.06.24 |
[백준 자바] 1016번(제곱 ㄴㄴ수) (0) | 2024.06.24 |