[자바] 1929번 소수 구하기

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

문제 

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

 

입력

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

 

출력

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

 

나의 문제 풀이

1) Scanner로 입력 받는 것도 좋지만 띄어쓰기도 있기 때문에 입력받은 내용을 한번에 묶어 전송하기 위해 BufferReader를 사용하였다.

2) 띄어쓰기가 있어 StringTokenizer를 사용하여 공백단위로 구분하여 순서대로 호줄하였다.

3) 소수가 여러개일수도 있어서 StringBuilder를 사용하였다.

4) String으로 받은 문자열을 int로 바꾸기 위해 Integer.parseInt를 사용하였다.

5) 0과 1은 소수가 아니기에 int i = 2 부터 시작하였다.

6) 에라토스테네스의 체의 알고리즘을 이용하여 다음과 같이 작성했다.

• 소수가 되는 수의 배수를 지우면 남은건 소수라는 알고리즘
• 2부터 구하고자 하는 구간의 수를 나열한다.
• 2는 소수이므로 2를 제외한 2의 배수를 모두 지운다.
• 3은 소수이므로 3을 제외한 3의 배수를 모두 지운다.

7) 위와 같은 과정을 반복하고 소수는 append 하였다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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(), " ");
        StringBuilder sb = new StringBuilder();

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int[] arr = new int[b + 1];

        for(int i = 2; i <= b; i++){
            arr[i] = i;
        }
        for(int i = 2; i <= b; i++){
            if(arr[i] == 0){
                continue;
            }
            for(int j = i+i; j <= b; j += i){
                arr[j] = 0;
            }
        }
        for(int i = a; i <= b; i++){
            if(arr[i] != 0){
                sb.append(i + "\n");
            }
        }
        System.out.println(sb);
    }
}