[1929] 소수 구하기

✔ 소수 구하기

[백준 1929]

문제 분석하기

N의 범위가 1000000이므로 일반적인 소수 구하기 방식으로 문제를 풀면 시간 초과가 발생

따라서 에라토스테네스 방법으로 문제를 풀이

손으로 풀어보기

1. 첫 번째 인덱스가 0인 것을 고려하여 크기가 N + 1인 배열을 선언한 후 값은 각각의 인덱스값으로 채움
2. 1은 소수가 아니므로 삭제
3. 2부터 N의 제곱근까지 값을 탐색하며 값이 인덱스값이면 그대로 두고, 그 값의 배수를 탐색해 0으로 변경
   • N이 a * b라고 가정했을 때, a와 b 모두 N이 제곱근보다 클 수 없으므로 N의 제곱근까지만 확인해도 전체 범위의 소수 판별 가능
4. 배열에 남아 있는 수 중 M 이상 N 이하의 수를 모두 출력

슈도코드 작성하기

M(시작 수) N(종료 수)
A(소수 배열)
for(N만큼 반복하기) {
    A 배열 초기화하기
}
for(N의 제곱근까지 반복하기) {
    소수가 아니면 넘어감
    for(소수의 배수 값을 N까지 반복하기) {
        이 수가 소수가 아니라는 것을 표시하기
    }
}
for(M ~ N까지 반복하기) {
    A 배열에서 소수인 값 출력하기
}

코드 구현하기

/**
 * 1929) 소수_구하기
 */
public class D037_1929 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // M(시작 수) N(종료 수)
        int M = sc.nextInt();
        int N = sc.nextInt();
        // A(소수 배열)
        int[] A = new int[N + 1];
        for (int i = 2; i <= N; i++) {
            // A 배열 초기화하기
            A[i] = i;
        }
        // N의 제곱근까지 반복하기
        for (int i = 2; i <= Math.sqrt(N); i++) {
            // 소수가 아니면 넘어감
            if (A[i] == 0) {
                continue;
            }
            // 소수의 배수 값을 N까지 반복하기
            for (int j = i + i; j <= N; j = j + i) {
                // 이 수가 소수가 아니라는 것을 표시하기
                A[j] = 0;
            }
        }
        // M ~ N까지 반복하기
        for (int i = M; i <= N; i++) {
            // A 배열에서 소수인 값 출력하기
            if (A[i] != 0) {
                System.out.println(A[i]);
            }
        }
    }
}