문제출처: https://www.acmicpc.net/problem/1929

문제 설명

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

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

입력

3 16

출력

3
5
7
11
13

문제 풀이

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

public class Main {
    public static void main (String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        StringBuilder sb = new StringBuilder();
        boolean [] notPrime = new boolean[b + 1];
        notPrime[0] = true;
        notPrime[1] = true;
        for(int i = 2; i < Math.sqrt(b + 1); i++) {
            if(notPrime[i]) continue;
            for(int j = i + i; j < b + 1; j += i)
                notPrime[j] = true;
        }
        for(int i = a; i < b + 1; i++) {
            if(!notPrime[i])
                sb.append(i).append('\n');
        }
        System.out.println(sb);
        br.close();
    }
}

지난번에 백준 - 베르트랑 공준 문제에서 본 고수의 풀이 방법을 적용해 보았습니다. boolean 배열을 활용해 소수를 찾아내는 방법을 적용하여 소수를 구해 보았고, StringBuilder를 활용하면 속도 효율이 가장 좋아서 적용해 보았습니다.