[백준] java 4134 다음 소수

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

문제

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

입력

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

풀이 과정

소수를 구하는 유명한 방법 중 에라토스테네스의 체가 있다. 에라토스테네스의 체는 다음과 같은 방법을 사용한다.
1. 찾고자 하는 범위의 자연수를 나열한다.
2. 1은 지운다.
3. 2부터 시작하여, 2의 배수를 지워나간다.
4. 다음 소수의 배수를 모두 지운다.
5. 남아있는 가장 작은 수(소수)에 대해 이 과정을 루트n보다 작거나 같은 소수까지 반복한다.

n이 소수인지 판별하기 위해선 위와 같은 방법을 사용할 수 있다. 나는 조금 다르게 작성하였다. 단순히 2부터 루트n까지 n을 나눠보고, 나누어떨어지는 경우가 있다면 n은 소수가 아니다.

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 i = 0; i < T; i++ ) {

			long n = Long.parseLong(br.readLine());

			while( true ){

				boolean isPrime = true;
				// 2부터 루트 n까지
				for( long j = 2; j*j <= n; j++ ){

					if( n % j == 0){
						isPrime = false;
						break;
					}
				}
				if( n >= 2 && isPrime) {
					sb.append(n).append("\n");
					break;
				}

				n++;

			}
		}
		System.out.println(sb);
	}
}

소수는 1과 자기 자신으로만 나누어떨어지는 수이다. 그러므로 2부터 루트n까지 나눠보고 나누어지지않으면 소수 나누어떨어지면 소수가 아니다.

출력 조건은 n보다 같거나 큰 소수를 구하는 것이다. n부터 소수인지 아닌지 판별한다. 만약 소수가 맞다면 n보다 같거나 큰 소수를 구했으므로 출력과 동시에 반복문을 벗어난다. 만약 n이 소수가 아니라면 n을 1씩 더해가며 재 반복한다.