4948. 베르트랑 공준 [JAVA]

Nak.s·2023년 2월 2일
0

CodeTest

목록 보기
19/19

위의 문제를 요약하면, 베르트랑 공준은 임의의 자연수 n에 대해
n과 2n 사이에는 무조건 소수가 존재하는 것을 뜻한다.

풀이는 아래와 같다.
이전에 풀었던 BackJoon 1929 소수구하기 문제에서
범위만 변경 됬을뿐이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//베르트랑 공준
//n 과 2n 사이의 소수 갯수 구하기
public class BJ_4948 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            int count = 0;
            int n = Integer.parseInt(br.readLine());
            if (n < 1 || n > 123456) return;
            if (n == 0) break;

            outer:
            for (int i = n + 1; i <= 2 * n; i++) {
                int dividend = (int) Math.sqrt(i); // 특정 수가 2개의 수의 곱이라 했을때 둘중하나는 무조건 제곱근보다 작거나 같다. 
                while (dividend > 1) {             // 그리고 특정 수의 소수인 약수들의 배수가 특정 수의 약수라면 그 특정수는 소수가 아니다.
                    if (i % dividend-- == 0) continue outer;
                }
                if (dividend == 1 && i != 1) ++count; // 나누기가 마무리 됬을때, 피제수가 1이라면 도중에 나눠떨어지는수가 없었다는걸 의미한다.
            }

            if(count == 0) return;
            System.out.println(count);
        }
    }
}
profile
궁금함이 많은 개발자

0개의 댓글