백준 알고리즘 1929번 : 소수구하기 (에라토스테네스의 체)

소수 구하기 성공분류

2 초

256 MB

84298

23559

16735

27.311%

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

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

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

답안

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.util.*;

public class Main {
    //baekjoon #1929
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()," ");
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        boolean[] table = new boolean[end+1];//true = isNotPrime false = isPrime
        table[0] = table[1] = true;
        for(int i = 2; i*i < table.length; i++){
            if(!table[i]){
                for(int j = i*i; j < table.length; j += i){
                    table[j] = true;
                }
            }
        }

        for(int i = start; i < table.length; i++){
            if(!table[i])System.out.println(i);
        }
    }
}

Note : 에라토스테네스를 사용할 경우 확인 범위가 제곱근으로 줄어들기 때문에 효율성이 향상된다.