[백준] 4134 - 다음 소수(JAVA)

1. 소요시간 : 25분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 4
4. 문제 유형 : 수학, 브루트포스 알고리즘, 정수론, 소수 판정
5. 다른 사람의 풀이를 참고 했는가 ? : O
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/4134
8. 푼 날짜 : 2023.03.20

1. 사용한 자료구조 & 알고리즘

BigInteger 클래스,
정수론을 사용했다.

2. 사고과정

입력이 40억 까지로 엄청 크다.

1. 우선 에라스토테네스의 체로 소수들을 모두 판별하여 담은 후, 다음 소수를 출력해보려고 했으나 메모리 256MB 에는 힘들 것 같았다. 그래서 PASS
2. 다음으로 내 현재 숫자에서 1씩 커지게 하면서 그 숫자가 소수인지 체크해주는 것이다. 그런데 이건 TLE 가 날 것이 분명했다. 그래서 PASS

이제 여기서 15분 동안 어떻게 해줘야 할지 고민했다. 답을 찾지 못했고
2번 과정으로라도 문제를 풀어보기로 했다. 제출한 결과는 역시나 TLE

결국 풀이를 보기로 했다.
BigInteger 클래스를 통해서 문제를 풀 수 있었다.

3. 풀이과정

1. 현재 숫자가 소수인지 판별. 소수라면 그냥 바로 출력하기.
2. 소수가 아니라는 것을 알았다면 BigInteger 클래스의 nextProbablePrime() 메소드로 다음 소수를 구한다.

4. 소스코드

import java.io.*;
import java.util.*;
import java.math.BigInteger;

public class Main {

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

		int t=Integer.parseInt(br.readLine());
		while(t-->0) {
			String num=br.readLine();
			BigInteger prime=new BigInteger(num);
			long val=Long.parseLong(num);
			long sqrt=(long) Math.sqrt(val);
			boolean s=false;
			for(int i=2;i<=sqrt;i++) {
				if(val%i==0) s=true;
			}
			if(s)
				sb.append(prime.nextProbablePrime());
			else if(val==0||val==1) {
				sb.append(prime.nextProbablePrime());
			}
			else
				sb.append(val);
			
			sb.append("\n");
			
			
			
		}
		System.out.println(sb);
		
	}
}

5. 결과

6. 회고

자료구조 & 알고리즘적으로 접근하지 못하고 클래스의 메소드를 이용해서 푼 문제라 풀고도 살짝 찝찝하다.
그리고 BigInteger 클래스는 알았어도 nextProbablePrime 메소드는 알지 못했는데 이번 기회에 확실하게 상기해야겠다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212