[BOJ] 1929 소수 구하기 - JAVA

1. 문제

1929번: 소수 구하기

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

---

2. 풀이

1.  1부터 N까지 소수인지 아닌지 판별하는 primeArr 배열을 만든다. 소수라면 false, 소수가 아니면 true를 저장한다.

2.  2부터 N까지 반복하면서 현재 숫자가 소수가 아니라면 다음으로 넘어간다.

3.  현재 숫자가 소수라면 배수에 접근해서 모두 소수가 아니라고 표시한다.(true표시) 이 때, 코드의 num<<1은 num*2이다.

4.  현재 숫자가 소수이고 M이상이라면 StringBuilder에 더한다. 

5.  N까지 반복을 끝낸 뒤 StringBuilder로 모은 문자열을 한 번에 출력한다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        boolean[] primeArr = new boolean[N+1];
        StringBuilder sb = new StringBuilder();

        for(int num=2;num<=N;num++){
            if(primeArr[num]) continue;

            if(num>=M) sb.append(num).append("\n");

            //num의 배수=소수가 아님
            for(int i=num<<1;i<=N;i+=num){
                primeArr[i] = true;
            }
        }

        System.out.print(sb);
    }
}

---

3. 결과