백준 JAVA 4948 베르트랑 공준

 

일반 소수풀이로 하면 시간초과가 나오므로 에라토스테네스의 체를 이용해야한다.

이전에 한번 써가면서 기장기본적인 에라토스테네스를 이해했는데 비슷한 유형을 안풀다보니 까먹어서 다시한번 이해하는 계기가 되었다.

 

배열을 만들어주어서 초기화를 하면 전부 false 값이 들어간다.

2의 배수 3의 배수 등등 은 true 값으로 변경해주면 되고 마지막에 false값=소수 를 전부 세어주면된다.

 

해당 문제를 접하고 다른 풀이를 보았을때 이해가 잘 안되었는데, 귀찮더라도 그림을 직접 그려가면서 F(false), T(true) 로 바꿔가면서 하면 그나마 이해가 쉬울것 같다.

 

백준1929 문제도 에라토스테네스의 체 를 이용해야하는 문제이므로 추가적으로 풀어보는 것이 좋겠다.

 

package BAEKJOON;

import java.util.Scanner;

public class NO1929_2 {
    public static void main(String[] args) {

        //에라토스테네스의 체를 이용하여 풀이
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();

        boolean[] isPrime = new boolean[N + 1];

        for (int i = 2; i < N; i++) {
            for (int j = i * i; j < N + 1; j += i) {
                isPrime[j] = true;
            }
        }
        for (int i = M; i < N+1; i++) {
            if(isPrime[i] == false) {
                System.out.println(i);
            }
        }
    }
}