BOJ 1929. 소수구하기

BOJ 1929. 소수 구하기

풀이

입력이 1 <= M <= N <= 1,000,000 이므로  소수 찾기  방식을 사용하면 시간 초과가 발생한다 시간 복잡도를 잘 계산하지 않으면 시간 초과가 발생하는것이다.

시간 복잡도를 줄이기 위해 에라토스테네스의 체 [wiki] 알고리즘을 사용한다

1~120까지 수가 있을 때  1을 제외한 지워지지 않은 가장 작은 소수는 2이다.

• 2의 배수를 모두 제거
• 3의 배수를 모두 제거
• 5의 배수를 모두 제거 … …

Java

import java.util.Scanner;

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

        boolean[] check = new boolean[1000001];
        StringBuilder sb = new StringBuilder();

        int min = sc.nextInt();
        int max = sc.nextInt();

        check[1] = true;

        for (int i = 2; i <= max; i++) {
            for (int j = 2; i * j <= max; j++) {
                if (!check[i * j]) {
                    check[i * j] = true;
                }
            }
        }

        for (int i = min; i <= max; i++) {
            if (!check[i]) {
                sb.append(i).append("\n");
            }
        }

        System.out.println(sb);
        sc.close();
    }
}

Kotlin

fun main() {
    val (m, n) = readLine()!!.split(' ').map { it.toInt() }
    val check = BooleanArray(n + 1) { false }
    for (i in 2..n) {
        if (!check[i]) {
            if (i > m) println(i)
            var j = 2
            while (i * j <= n) {
                check[i * j] = true
                j++
            }
        }
    }
}

풀이소스

github.com/beomjo/algorithm-study/blob/main/BOJ/java/1929.java github.com/beomjo/algorithm-study/blob/main/BOJ/kotlin/1929.kt