[백준] 4134번 - 다음 소수 [Java][C++]

문제 링크

---

1. 문제 풀이

정수 $n$ 이 최대 $4 \times 10^9$ 일 때, $n$ 보다 크거나 같은 가장 작은 소수를 찾는 문제로 $n$ 이 소수가 아니면 $n + 1$ 을 한 후 소수인지 판정하는 과정을 반복하는 브루트 포스로 찾아나가면 해결할 수 있다. 이때 $n$ 의 제곱근까지만 나누어보는 것으로 소수를 판정하는 계산량을 줄일 수 있다.

---

2. 코드

1. 브루트 포스 [Java]

$n$ 이 $0$ 또는 $1$ 일 때는 $2$ 를 출력하도록 예외처리를 해줬다.

import java.io.*;

public class Main {
    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 tc = 1; tc <= T; tc++) {
            long N = Long.parseLong(br.readLine());

            if (N <= 1) {
                sb.append("2\n");
                continue;
            }

            out:
            while (true) {
                for (long i = 2; i * i <= N; i++) {
                    if (N % i == 0) {
                        N++;
                        continue out;
                    }
                }

                sb.append(N).append("\n");
                break;
            }
        }

        System.out.print(sb);
    }
}

2. 브루트 포스 [C++]

$n$ 이 $0$ 또는 $1$ 일 때는 $2$ 를 출력하도록 예외처리를 해줬다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    for (int tc = 1; tc <= t; tc++) {
        long long n;
        cin >> n;

        if (n <= 1) {
            cout << 2 << '\n';
            continue;
        }

        while (true) {
            bool isPrime = true;
            for (long long i = 2; i * i <= n; i++) {
                if (n % i == 0) {
                    isPrime = false;
                    n++;
                    break;
                }
            }

            if (isPrime) break;
        }

        cout << n << '\n';
    }
}

---

3. 풀이 정보

1. 브루트 포스 [Java]

언어	시간	메모리	코드 길이
Java 11	348 ms	14420 KB	850 B

2. 브루트 포스 [C++]

언어	시간	메모리	코드 길이
C++ 17	212 ms	2020 KB	649 B

---