BOJ_4948 : 베르트랑 공준

👉 문제링크

4948번: 베르트랑 공준

---

---

🔸 문제 분석 🔸

• 입력 된 수 n보다 크고 2n이하인 소수의 개수를 출력한다.
• 0이 입력 될 때까지 반복한다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
	private static Scanner sc;

	public static void main(String[] args) {
		sc = new Scanner(System.in);
		int n = sc.nextInt();

		while (n != 0) {
			boolean[] arr = new boolean[n * 2 + 1];
			for (int i = 2; i <= n * 2; i++) {
				if (!arr[i]) {
					int j = 2;
					while (i * j <= n * 2) {
						arr[i * j] = true;
						j++;
					}
				}
			}

			int answer = 0;
			for (int i = n + 1; i <= n * 2; i++) {
				if (!arr[i]) {
					answer++;
				}
			}
			System.out.println(answer);

			n = sc.nextInt();
		}
	}
}

🔸 코드 해석 🔸

• 2부터 2n까지의 소수를 boolean배열 arr에 채운다.
  • 2부터 2*n까지 수를 증가해 가며 소수를 판별한다.
    • 한 수를 2부터 값이 n*2를 넘지 않을 때 까지 키워가며 arr값을 true로 바꾼다.
  • 시작 수가 이미 true일 때는 반복을 시작하지 않는다.
• arr를 순회해 false의 수를 세서 출력한다.

---

🔸 end 🔸

• 소수를 배열에 저장해 계산 속도를 올리는 아이디어를 알고있어서 쉽게 풀 수 있었다.