[Do It! 코딩테스트 자바편(김종관)] 문제 037(백준: 1929번)

난이도

에라토스테네스의 체를 이해하고 구현만 하면 되서 크게 어렵지 않았지만, 처음 이를 접하고 구현하려고 해서 처음 시도 땐 실패했다. 다시 수정해서 성공했다.

문제

n의 제곱근까지만 탐색하는 이유를 교재 설명으로는 도저히 이해할 수 없었다. 아래 블로그 글이 이해하는 데 도움을 주었다. - 참고 블로그

소수 구하기(백준: 1929번)

풀이

import java.util.Scanner;

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

        int[] a = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            a[i] = i;
        }

        // 에라토스테네스의 체
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (a[i] == 0)
                continue;
            for (int j = 2 * i; j <= n; j += i)
                a[j] = 0;
        }

        for (int i = m; i <= n; i++) {
            if (a[i] != 0)
                System.out.println(a[i]);
        }
        sc.close();
    }
}