[백준-4948번/Java] 베르트랑 공준

* 소수 판별

* 제곱근 범위 나누기법 사용함.

; 소수 여부를 검사할 수에 대해서 그 값의 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어나므로 제곱근 이하의 작은 값까지만 검사를 하면 나머지는 검사를 할 필요가 없다.

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);

		int[] arr = new int[123456 * 2 + 1];

		for (int i = 1; i < arr.length; i++) {
			if (i == 1) {
				arr[i] = -1;
			} else {
				arr[i] = i;
			}
		}

		// 제곱근 범위 나누기
		for (int i = 3; i < arr.length; i++) {
			for (int j = 2; j <= Math.sqrt(i); j++) {
				if (i != j && i % j == 0) {
					arr[i] = -1;
				}
			}
		}

		while (true) {
			int n = scan.nextInt();

			if (n == 0)
				break;

			int count = 0;
			for (int i = n + 1; i <= n * 2; i++) {
				if (arr[i] != -1) {
					count++;
				}
			}

			System.out.println(count);

		}
		scan.close();
	}

}