[백준 자바] 24039번(2021은 무엇이 특별할까?) - 연속한 두 소수의 곱

난이도 - 실버 5

문제

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

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

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

입력

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

출력

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

제한

•  1≤𝑁≤10000$1 \le N \le 10\,000$ 
•  𝑁$N$은 정수이다.

 

---

 

728x90

소수로만 구성된 배열을 생성하고(primes), 연속한 두 소수의 곱이 N보다 커질 때까지 primes 배열을 순회한다.

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

public class Main {
  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());

    bw.write(String.valueOf(specialNum(N, 110)));

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

  static int specialNum(int N, int max) {
    boolean[] isPrime = sieveOfEratosthenes(max);
    ArrayList<Integer> primes = new ArrayList<>();

    for (int i = 2; i < isPrime.length; i++) {
      if (!isPrime[i])
        primes.add(i);
    }

    for (int i = 1; i < primes.size(); i++) {
      if (primes.get(i - 1) * primes.get(i) > N)
        return primes.get(i - 1) * primes.get(i);
    }

    return 0;
  }

  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;
  }
}