[Java] 5단계. 다음 소수 [4134번]

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

• 예제 입력1

3
6
20
100

• 예제 출력1

7
23
101

---

• 문제 접근
  • 입력
    
    • 첫째 줄 : 테스트 케이스 개수 T
    • ~ T번째 줄 : 정수 n (0 <= n <= 40억)
  • 출력
    • 각각의 테스트 케이스에 대해 n이상의 가장 작은 소수를 한 줄씩 출력
• 문제 해결
  • 정수 n은 최대 40억까지 입력이 가능하기 때문에 int의 범위를 벗어나 long을 사용해야 함
  • 소수인지 아닌지 판별하는 check 메서드의 조건
    
    • 0과 1은 소수가 아님
    • 2는 소수
    • n % 2 == 0에서 짝수는 모두 걸러졌기 때문에 i = 3부터 시작하고 2씩 증가시킴
      → 반복문의 횟수를 줄이기 위함
      
    • 조건식은 루트n까지
      → 반복문의 횟수를 줄이기 위함
      
    • ex) n = 121
      • 121 % 3 != 0
      • 121 % 5 != 0
      • 121 % 7 != 0
      • 121 % 9 != 0
      • 121 % 11 == 0 → 121은 소수가 아님
    • ex) n = 123 → 루트 123 : 11.090536
      • 123 % 3 != 0
      • 123 % 5 != 0
      • 123 % 7 != 0
      • 123 % 9 != 0
      • 123 % 11 != 0
      • 13^2 = 169이기 때문에 조건식이 i <= Math.square(123)인 것
• 기존 풀이 [메모리 : 14,304 KB / 시간 : 240 ms]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    int T = Integer.parseInt(br.readLine());
    for (int i = 0; i < T; i++) {
        long n = Long.parseLong(br.readLine());
        while (!check(n)) {
            n++;
        }
        sb.append(n).append("\n");
    }
    System.out.println(sb);
}

private static boolean check(long n) {
    if(n == 2) return true;
    if (n == 1 || n % 2 == 0) return false;
    for (long i = 3; i <= Math.sqrt(n); i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}