[백준] 소수 구하기 - 1929번

문제설명

www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

 

기본아이디어

M과 N 범위 안에 있는 소수 구하기. N, M이 크지 않기 때문에 간단하게 boolean형 배열을 만들고 2 ~ N 까지 값을 증가시키면서 소수인 값은 자신의 배수에 해당하는 위치를 true로 만들어 줬습니다. M ~ N 까지 값을 소수인지 판별할 수 도 있었지만 최악의 경우를 따졌을 때 (M:1, N:1,000,000) 성능면에서 크게 차이나지 않는것 같아 이렇게 풀었습니다.

 

풀고 나서 보니까 예전에 풀었던 문제였습니다;; 아무튼 시간면에서 크게 차이나는 이유는 두번째 풀었을 때는 소수인게 판별나면, 즉 접근했을 때 값이 false 이면 바로 output (= StringBuilder)에 넣어주었기 때문입니다.

구현코드

    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
 
        StringTokenizer str = new StringTokenizer(input.readLine());
        int M = Integer.parseInt(str.nextToken());
        int N = Integer.parseInt(str.nextToken());
 
        boolean[] numbers = new boolean[N+1];
    
        for(int i = 2; i <= N; i++){
            if(!numbers[i]){
                int temp = i * 2;
                while(temp <= N){
                    numbers[temp] = true;
                    temp += i;
                }
                if(i >= M){
                    output.append(i + "\n");
                }
            }
        }
        System.out.println(output);
    }

 

 

정리, 기억할 내용

1. 입력값의 범위를 잘 파악하자.2. boolean 배열은 좋다!