[Java] 백준 24039번 - 2021은 무엇이 특별할까?

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 소수
 - 에라토스테네스의 체

 

https://www.acmicpc.net/problem/24039

 

문제

백준 온라인 저지의 송년대회 Good Bye BOJ, 2021!의 개최일은 2021년 12월 31일이다. 원이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2021이 무언가 특별하다는 사실을 깨달았다.

그렇다. 2021은 연속한 두 소수 43과 47의 곱이다. 다음에 이런년도가 오려면 무려 470년 뒤인 2491년이 되어야 한다. 원이는 어떤 수가 연속한 두 소수의 곱으로 이루어져 있으면 특별한 수라 부르기로 하였다.

주어진 수보다 큰 특별한 수 중 가장 작은 수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 주어진 수 $N$이 주어진다.

출력

첫 번째 줄에 $N$보다 큰 특별한 수 중 가장 작은 수를 출력하여라.

 

---

 

에라토스테네스의 체를 이용해 소수 목록을 구한 다음 인접한 두 곱셈중 주어진 수보다 크며 가장 작은 소수의 곱을 구하는 문제이다.

 

import java.io.*;
import java.util.*;

public class Main {	
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		
		int [] isPrime = new int[n+1];
		
		int sqrt = (int) Math.sqrt((double)n+1);
		isPrime[0] = 2;
		isPrime[1] = 2;
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		for(int i=2; i<sqrt+1; i++) {
			if(isPrime[i] == 0) {
				for(int j = i+i; j<n+1; j += i) {
					isPrime[j] = 2;
				}
			}
		}
		
		for(int i=2; i<n+1; i++) {
			if(isPrime[i] == 0) {
				list.add(i);
			}
		}
		
		int result = Integer.MAX_VALUE;
		for(int i=0; i<list.size()-1; i++) {
			int tmp = list.get(i) * list.get(i+1);
			if(tmp > n && result > tmp) {
				result = tmp;
				break;
			}
		}
		if(result == Integer.MAX_VALUE) {
			System.out.println(6);
		} else {
			System.out.println(result);
		}
	}
}

 

N = 1 인경우나 N = 2인 경우

소수의 목록으로 곱셈을 할 수 없기 때문에, 가장 작은 소수의 곱인 2 x 3 = 6의 결과를 리턴한다.