[백준] 1929번: 소수 구하기 (Java)

1. 문제설명

M이상 N이하의 소수를 모두 출력하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 256MB

 

2. 접근 방식

• 소수: 1과 자기 자신만을 약수로 가지는 수
• 에라토스테네스의 체 알고리즘을 사용한다. (https://propercoding.tistory.com/182)
  • 2부터 $\sqrt{N}$까지의 소수의 배수를 제거하여 소수를 판별한다.
• boolean 배열을 사용하여 N까지 수의 소수 여부 저장한다. (false: 소수, true: 합성수)
• M부터 N까지 소수인 수를 출력한다.

 

3. 틀린 이유

for(int i=M; i<=N; i++) {
    cnt = 0;
    sqrt = (int)Math.sqrt(i);
    for(int j=1; j<=sqrt; j++) { // ex: i=36, j=6
        if(i % j == 0) {
            // j=1,2,3,4,6 => 약수: 1,2,3,4,6
            cnt++;
            if(i / j != j) {
                // j가 약수이면 i/j도 약수
                // j가 i의 제곱근이 아닐 경우
                // j=1,2,3,4 => 약수: 36,18,12,9
                cnt++;
            }
        }
    }
    if(i!=1 && cnt==2) { // 1을 제외하고 약수 2개를 가지는 수
        System.out.println(i);
    }
}

에라토스테네스의 체 알고리즘을 사용하지 않고, 단순히 약수의 개수를 구하는 방법을 사용했다. 

 

3. 최종 코드

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 M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        boolean[] isComposite = new boolean[N+1]; // false: 소수, true: 합성수
        isComposite[0] = isComposite[1] = true; // 0, 1는 소수가 아님

        // 에라토스테네스의 체 알고리즘 사용
        for(int i=2; i*i<=N; i++) {
            if(!isComposite[i]) { // i가 소수인 경우
                for(int j=i*i; j<=N; j+=i) { // i의 배수들을 합성수로 표시
                    isComposite[j] = true;
                }
            }
        }

        for(int i=M; i<=N; i++) {
            if(!isComposite[i]) // 소수인 수를 출력
                System.out.println(i);
        }
    }
}