JAVA백준 문제풀이 (12) 4948:베르트랑 공준

 

 

단계별로 문제를 풀다보니 한 번 특정 형태의 문제를 만나면 해당 문제만 연달아 일주일가량 만나게 된다.

그래서 오늘도 어김없이 에라토스테네스의 체와 관련된 소수를 구하는 문제다.

 

매번 똑같은 내용으로 글을 늘어지게 작성할 수는 있지만.. 의미가 없다.

에라토스테네스의 체는 굉장히 쉽기 때문에 꼭 직접 풀어보길 바란다.

 

 

https://7357.tistory.com/104?category=1065986 

0부터 n까지의 수 중 소수 구하기 : 에라토스테네스의 체

 

 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        boolean[] isCompositeNum = new boolean[246913];
        isCompositeNum[0] = isCompositeNum[1] = true;
        // 0과 1은 합성수가 아닙니다. 임의 적용.

        for (int i=0; i*i<=isCompositeNum.length; i++) {
            if (!isCompositeNum[i]) {
                for (int j=i*i; j<= isCompositeNum.length; j+=i) {
                    isCompositeNum[j] = true;
                }
            }
        }
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            int inputNum = Integer.parseInt(br.readLine());
            int result = 0;
            if (inputNum == 0) { break; }

            for (int i=inputNum+1; i<=(inputNum*2); i++) {
                if (!isCompositeNum[i]) { result +=1; }
            }
            System.out.println(result);
        }
    }
}

 

 

+ 속도를 최대한 빠르게 하는 방법이 있다.

 

참고한 블로그

https://st-lab.tistory.com/85

[백준] 4948번 : 베르트랑 공준 - JAVA [자바]

매번 인풋을 받고 배열을 체크하며 숫자를 세는 것이 아니라, 처음부터 각 인덱스까지의 소수 개수를 체크해놓은 뒤 입력 값을 받으면 해당하는 개수를 출력해주는 것이다. 항상 똑같은 방법으로 풀지 말고 다양한 풀이에 도전해보자.