백준 1929 [소수 구하기]

'에라토스테네스의 체' 알고리즘을 이용한 문제풀이 예제이다.

백준 1929 [소수 구하기] 라는 문제이다.

 

---

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int nStart = Integer.parseInt(st.nextToken());
		int nEnd = Integer.parseInt(st.nextToken());
		
		boolean[] bNumber = new boolean[nEnd+1];
		//소수x : flase , 소수o : true
        
		//1은 소수가 아니기때문에 true
		bNumber[1] = true;  
        
		//제곱근
		int nSqrt = (int)Math.sqrt(nEnd);
		
		for(int nIdx = 2 ; nIdx <= nSqrt ; nIdx++) {
			if(bNumber[nIdx] == false) {
				//소수의 배수 제거
				for(int nMultiple = nIdx + nIdx ; nMultiple < nEnd + 1 ; nMultiple += nIdx) {
					bNumber[nMultiple] = true;
				}
			}
		}
		
		//소수 출력
		for(int nIdx = nStart ; nIdx < bNumber.length; nIdx++) {
			if(bNumber[nIdx] == false) {
				bw.write(nIdx+"\n");
			}
		}
		bw.close();
	}

}

---

코드리뷰

//제곱근
int nSqrt = (int)Math.sqrt(nEnd);
		
for(int nIdx = 2 ; nIdx <= nSqrt ; nIdx++) {
	if(bNumber[nIdx] == false) {
		//소수의 배수 제거
		for(int nMultiple = nIdx + nIdx ; nMultiple < nEnd + 1 ; nMultiple += nIdx) {
			bNumber[nMultiple] = true;
		}
	}
}

'소수인지 먼저 확인해야 하지 않나?' 라는 생각이 들것이다. 필자도 처음에는 그렇게 생각하였다.

다른 사람들의 소스를 리뷰하면서 위 매커니즘을 이해하였다.

 

반복문의 시작을 입력받은 정수를 사용하지 않고 2부터 시작하게하였다.

2부터 시작한다면 어떤 수를 입력 받더라도 소수인지 확인하는 로직이 들어가지 않아도 된다.

 

bNumber[1] = true;

입력받는 두 정수의 범위가 (1 ≤ M ≤ N ≤ 1,000,000) 이기 때문에 필히 예외처리를 해주어야한다. 

1은 소수가 아니기 때문.

 

 

---

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

Scanner를 사용하지 않고 BufferedReader를 사용하는 이유

BufferedReader / Scanner 와의 속도차이