[문제] 백준 1929번 소수 구하기 - 에라토스테네스의 체 이용하기

* 출처: 백준 단계별로 풀어보기 기본 수학 2

www.acmicpc.net/problem/1929

[

1929번: 소수 구하기

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

www.acmicpc.net

](https://www.acmicpc.net/problem/1929)

import java.io.*;
import java.util.StringTokenizer;


public class Main {
    public static boolean[] prime;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        prime = new boolean[N+1];
        getPrime(N);

        for(int i=M;i<=N;i++) {
            if(!prime[i])
                sb.append(i).append('\n');
        }

        System.out.println(sb);
    }
    public static void getPrime(int n) {
        if(n<2) return;

        prime[0] = prime[1] = true;

        for(int i=2;i<=Math.sqrt(n);i++) {
            if(prime[i])
                continue;

            for(int j=i*i;j<=n;j+=i) {
                prime[j] = true;
            }
        }
    }
}

에라토스테네스의 체를 이용해서 시간복잡도를 줄여야 한다.