📌 문제

[4134] 다음 소수

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

⬇️ 입력

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

⬆️ 출력

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

💡 코드

✅ 처음에는 이전에 풀었던 소수 문제처럼 num을 입력받아서 num 제곱근까지의 수 중 어떤 수로 나누어 떨어지면 소수가 아니라 판정하여 num을 계속 증가시켜 num이 소수일 때 반복문을 멈춘다! 라는 알고리즘을 생각했다가 입력값 범위가 40억인거 보고 이건 500퍼 시간초과 뜨겠다,, 싶어서 포기,, 하고 결국 오늘도 구글링을 찾아 헤매다,,

Java에는 BigIntaeger라는 클래스가 존재하는데, 이는 int, long 타입으로 담을 수 없는 무한의 숫자를 문자열 타입으로 받아서 사용할 수 있다. 거기에 해당 클래스에서 제공하는 메서드를 사용하면 소수 판별이 더욱 간단해진다!

• isProbalbePrime(10) : 현재 값이 소수인지 판단하는 메서드 ➡️ 매개변수로 10을 주면 판별률이 99.9%라고 한다.
• nextProbablePrime() : 현재 값보다 큰 다음 소수
  
  해당 메서드들을 사용하면 코드 자체는 간결해져서 좋은데, 아무래도 새로운 클래스를 선언해서 쓰다 보니 메모리나 시간을 많이 잡아먹는다는 단점은 존재한다..

import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int t = Integer.parseInt(br.readLine());
		for(int i=0;i<t;i++) {
			BigInteger num = new BigInteger(br.readLine());
			
			if(num.isProbablePrime(10)) sb.append(num + "\n");
			else sb.append(num.nextProbablePrime() + "\n");
		}
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
}

➕ 혹시나 해서 처음 생각했던 방법도 제출해봤는데 의외로 정답이였다,, 심지어 메모리랑 시간도 훨씬 적게 잡아먹음,,!

import java.io.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int t = Integer.parseInt(br.readLine());
		for(int i=0;i<t;i++) {
			long num = Long.parseLong(br.readLine());
			if(num <= 2) {
				sb.append(2).append("\n"); continue;
			}
			
			boolean isPrime = false;
			while(!isPrime) {
				isPrime = true;
				
				for(long j=2;j<=Math.sqrt(num);j++) {
					if(num % j == 0) {
						isPrime = false; break;
					}
				}
				if(!isPrime) num++;
				else sb.append(num).append("\n");
			}
		}
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
}