[백준][BOJ 4134] - 다음 소수

문제

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

4134번: 다음 소수

 

 

문제 접근

• $N$보다 크거나 같은 소수 중 가장 작은 소수를 구하는 문제
• $N$이 최대 4억까지 주어질 수 있고, 어디까지 진행되는지도 알 수 없기 때문에 수 자체는 넉넉하게 long으로 잡았다. 생각해보면 그냥 int도 21억까지 지원하기 때문에 int로 해도 무방할 것 같기도 하다
• 이후에는 N을 1씩 증가시키며 소수인지를 판별했다.
  • 소수를 판별하는 방식은 여러가지가 있지만 나는 루트를 적용하여 범위를 줄이는 방식을 사용하였다.

 

 

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());

    for (int testCase = 0; testCase < T; testCase++){
      long N = Long.parseLong(br.readLine());

      if (N <= 2){
        System.out.println(2);
        continue;
      }

      while(true){
        boolean flag = true;

        for (int i = 2; i < Math.sqrt(N) + 1; i++){
          if (N % i == 0){
            flag = false;
            break;
          }
        }

        if (flag) {
          System.out.println(N);
          break;
        }

        N++;
      }
    }
  }
}