[java] boj 1929 소수찾기 - 에라토스테네스의 체

소수 구하기 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

140139

39260

27742

26.838%

문제

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

입력

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

출력

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

예제 입력 1 복사

3 16

예제 출력 1 복사

3
5
7
11
13

package solved.Class;

import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.TreeSet;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String s[] = br.readLine().split(" ");

        int start = Integer.parseInt(s[0]);
        int end = Integer.parseInt(s[1]);


        boolean list[] = new boolean[end+1];
        list[0] = true;
        list[1] = true;
        for(int i=2;i<=Math.sqrt(end);i++){
            if(!list[i]){
                check(i,list);
            }
        }

        for(int i=start;i<=end;i++)
            if(!list[i])
                bw.append(i+"\n");
        bw.flush();

    }

    public static void check(int index, boolean[] list){
        for(int i=index+1;i<list.length;i++){
            if(list[i])
                continue;
            if(i%index==0)
                list[i]=true;
        }
    }
}