BOJ01929 소수 구하기

https://www.acmicpc.net/problem/1929 (opens new window)

M 이상 N 이하의 소수를 모두 출력한다.

에라토스테네스의 체

에라토스테네스의 체는 가장 대표적인 소수 판별 알고리즘이다.

소수란? '양의 정수를 두 개만 가지고 있는 자연수'

이러한 소수를 대량으로 빠르게 획득할 수 있는 방법은 에라토스테네스의 체를 사용하는 것이다.

private static void primeNumberSieve() {
    for (int i = 2; i <= 1_000_000; i++) {
        numbers[i] = i;
    }

    for (int i = 2; i <= 1_000_000; i++) {
        if (numbers[i] == 0) {
            continue;
        }

        for (int j = i + i; j <= 1_000_000; j+= i) {
            numbers[j] = 0;
        }
    }
}

제출 코드

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ1929 {

    static long[] numbers = new long[1_000_001];

    private static void primeNumberSieve() {
        for (int i = 2; i <= 1_000_000; i++) {
            numbers[i] = i;
        }

        for (int i = 2; i <= 1_000_000; i++) {
            if (numbers[i] == 0) {
                continue;
            }

            for (int j = i + i; j <= 1_000_000; j+= i) {
                numbers[j] = 0;
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int m = scanner.nextInt();
        int n = scanner.nextInt();

        primeNumberSieve();

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = m; i <= n; i++) {
            if (numbers[i] != 0) {
                stringBuilder.append(i).append("\n");
            }
        }

        System.out.println(stringBuilder);
    }
}

References.

에라토스테네스의 체 (opens new window)

#algorithm #BOJ #수학 #정수론 #소수 판정 #에라토스테네스의 체