[Baekjoon] 9753_짝 곱

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

---

< 짝 곱 >

 

문제 풀이 

 

미리 100,000까지 소수를 구한다. 서로 다른 소수의 곱을 구해 ArrayList에 저장하여 정렬 후 K보다 크거나 같은 값 중에서 가장 작은 값을 출력한다.    

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

public class _9753_ { // 짝 곱

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

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

		boolean arr[] = new boolean[100001];
		for (int i = 2; i <= Math.sqrt(100001); i++) {
			if (!arr[i]) {
				for (int j = i * i; j < 100001; j += i) {
					arr[j] = true;
				}
			}
		}

		ArrayList<Integer> result = new ArrayList<>();
		for (int i = 2; i < 100001; i++) {
			if (arr[i]) {
				continue;
			}
			for (int j = i + 1; j < 100001; j++) {
				if (arr[j]) {
					continue;
				}
				if ((long) i * (long) j > 100001) {
					break;
				}
				result.add(i * j);
			}
		}
		Collections.sort(result);

		for (int i = 0; i < T; i++) {
			int K = Integer.parseInt(bf.readLine());
			for (int num : result) {
				if (num >= K) {
					bw.write(num + "\n");
					break;
				}
			}
		}
		bw.flush();
	}
}

변수)
T : 테스트 케이스의 개수
arr : 소수 판별
result : 서로 다른 소수의 곱을 저장한 ArrayList

 

테스트 케이스의 개수를 입력받는다. 먼저 2부터 100000까지 소수를 판별한다. 서로 다른 소수의 곱을 구해 ArrayList에 저장한 후 정렬한다. K를 입력받아 ArrayList를 탐색하며 K보다 크거나 같은 수 중에서 가장 작은 값을 출력한다.

---

---