백준 JAVA 1929 소수 구하기

에라토스테네스의 체를 사용하는 문제이다.

 

어려워서 해당 알고리즘을 사용하는 다른문제랑 10번은 쳐봤더니 공식이 외워진거같다

물론 안쓰면 까먹겠지만, 가끔 체크하고 풀어봐야겠다.

 

반복문을 돌때, 제곱근으로 왜 해야하지 했는데, 다른 블로그를 보고 이해가 갔다.

j 에서 i를 제곱으로 계산하고 쓰기 때문이였다.

 

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];
        isPrime[0] = true;
        isPrime[1] = true;

        for (int i = 2; i < Math.sqrt(N+1); i++) {
            // j 에서 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);
            }
        }
    }
}