[백준] 4143번: 다음 소수

📌 문제

---

정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

📌 입력

---

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

📌 출력

---

각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

📌 풀이

---

생각보다 단순해보이는 문제였다. 소수인지 확인하는 로직은 생각보다 쉬웠기 때문에 바로 코드를 작성해보았다.

1. 테스트 케이스 별로 숫자를 받는다.
2. search() 함수에 인자로 넘겨준다.

소수인지 판별할때 while문을 사용할까 했는데 그럴 필요가 없었다.

3. 넘겨준 인자가 1일 경우 로직에 문제가 생기기 때문에 1이 아닌 경우에 for문으로 들어간다.
4. 넘겨받은 인자만큼 1부터 반복을 시작하는데 % 연산자를 이용해서 나머지가 0인지 확인한다.
5. 나머지가 0일 경우 소수가 아니라는 의미이므로 인자를 1증가 시키고 i=1을 통해 다시 조회한다.

수정 전 코드

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

public class Main

    public static long search(long n){
        if(n!=1){
            for(int i=1; i<=n/2; i++){
                if(n%i == 0) {
                    n++;
                    i=1;
                }
            }
        }
        return n;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        long n;
        for(int i=0; i<T; i++){
            n = Long.parseLong(br.readLine());
            System.out.println(search(n));
        }
    }
}

그 결과...

런타임 에러가 떴다... 😭😭

문제를 잘 읽어보니 큰 수의 정수가 주어질 수 있다는 사실을 깨달았다.
이전에도 비슷한 경우가 있어 모든 변수 타입을 long으로 바꾸고 Long.parseLong(br.readLine()) 또한 바꾸었다.

그리고 다시 제출한 결과...

이번에는 시간 초과가 나왔다..... 😡😡
직접 로직을 짜서 풀어보려고 했지만 아마 for문에서 시간 초과가 나오는거 같아 BigInteger를 사용하기로 결정했다.

BigInteger에는 다음과 같은 메소드를 제공한다.

• isProbablePrime() : 현재 값이 소수인지 아닌지 판단하는 메소드
• nextProbablePrime() : 다음 소수 값을 반환해주는 메소드

참고 : BigInteger을 초기화하기 위해서는 문자열을 인자 값으로 넘겨주어야 한다.

그렇게 로직을 수정하고 제출하니

드디어 성공했다!! 😀😀

이를 통해 BigInteger라는 것의 존재를 알게 되었고 .isProbablePrime(10)과 .nextProbablePrime()를 통해 소수를 구할 수 있다는 것을 알게되었다!!

📌 최종 코드

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

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());
        long n;
        for(int i=0; i<T; i++){
            n = Long.parseLong(br.readLine());
            BigInteger bigInt = new BigInteger(String.valueOf(n));
            if (bigInt.isProbablePrime(10)) {
                System.out.println(bigInt);
            }
            else {
                System.out.println(bigInt.nextProbablePrime());
            }
        }
    }
}

문제 링크 : 4143번: 다음 소수