[Baekjoon] 21919_소수 최소 공배수

Silver III

문제(출처: https://www.acmicpc.net/problem/21919)

---

< 소수 최소 공배수 >

 

문제 풀이 

 

에라토스테네스의 체를 활용하여 먼저 소수를 구한다. 수열 A를 입력받으면서 소수들의 최소공배수를 구하기 위해 중복되지 않은 소수 값을 곱한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class _21919_ { // 소수 최소 공배수

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		boolean arr[] = new boolean[1000001];
		arr[0] = true;
		arr[1] = true;
		for (int i = 2; i < 500001; i++) {
			if (!arr[i]) {
				for (int j = i + i; j < 1000001; j += i) {
					arr[j] = true;
				}
			}
		}

		Set<Integer> set = new HashSet<>();
		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(st.nextToken());
			if (!arr[num]) {
				set.add(num);
			}
		}

		if (set.size() == 0)
			System.out.println(-1);
		else {
			long result = 1;
			for (int num : set) {
				result *= num;
			}
			System.out.println(result);
		}
	}
}

변수)
n : 수열의 길이
arr : 소수
set : 수열 A 값 중 소수
result : 소수들의 최소공배수

 

수열 A의 길이 n을 입력받는다. 에라토스테네스의 체를 활용하여 소수를 미리 구한다. 수열 A의 값을 입력받으면서 소수인 값을 set에 저장한다. 여기서 set을 사용하는 이유는 중복처리를 위해서다. set의 크기가 0이라면 소수가 없는 경우이므로 -1을 출력하고 set의 크기가 0이 아니면 set에 있는 값을 다 곱한 값을 출력한다.

---

---