[BOJ] [JAVA] 4134번 다음 소수

4134번: 다음 소수

자연수 n 이하의 소수의 개수를 찾는 문제를 에라토스테네스의 체를 이용하여 푼 적이 있다.

[Programmers][Python] 소수 찾기

이번 문제는 주어진 수 n보다 크거나 같은 수 중 가장 작은 소수를 찾는 문제이다.

n은 4*10^9보다 작거나 같은 자연수이다.

때문에 그의 제곱근인 63246보다 작은 수들에 대해 각 수가 소수인지 판단하는 bool array를 만들었다.

다시 생각해보니 63247보다 큰 수까지도 array에 넣었어야 할 것 같다.

그 다음 수 n을 받아서 n을 63246보다 작은 소수로 나누었을 때 나머지가 0이면 n++을 하고 다시 수행,

63246보다 작은 모든 소수에 대하여 나머지가 0인 경우가 없었다면 n을 소수로 판별했다.

package orgs.BOJ;

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		/*
		System.out.print(Math.sqrt(4 * Math.pow(10,  9)));
		63245.553203367585
		*/
		boolean [] isNotPrime = new boolean[63247];
		isNotPrime[0] = isNotPrime[1] = true;
		
		for (int i = 2; i < 63247; i++) {
			if (!isNotPrime[i]) {
				int j = i;
				while (j <= 63247 - i) {
					j += i;
					isNotPrime[j] = true;
				}
			}
		}
		for (int i = 0; i < n; i++) {
			long a = sc.nextLong();
			if (a <= 63246) {
				while (true) {
					if (!isNotPrime[(int) a]) {
						System.out.println(a);
						break;
					}
					a++;
				}
			} else {
				while (true) {
					for (int k = 2; k <= Math.sqrt(a);) {
						if (!isNotPrime[k]) {
							if (a % k == 0) {
								a++;
								k = 2;
								continue;
							}
						}
						k++;
					}
					System.out.println(a);
					break;
				}
			}
		}
		sc.close();
	}
}