[Baekjoon(JAVA) - Algorithm] 2581번: 소수

https://www.acmicpc.net/problem/2581

 

---

문제를 풀기 앞서,

소수는 1과 자기 자신만을 약수로 가져야 한다.

이전에 풀었던 소수 문제는 숫자 하나에 대해서 그 숫자가 소수인지를 판별했지만

이 문제는 여러 소수를 찾는 문제이다.

 

여러 소수를 찾을 때는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용하면 편하다.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity

에라토스테네스의 체는 주어진 한계까지 모든 소수를 찾는 고대 알고리즘이다.

이 방법으로 주어진 정수 N 보다 작거나 같은 모든 소수를 찾으려면

• 2로 시작하여 2의 배수를 제외시킨다.
• 3으로 시작하여 3의 배수를 제외시킨다. (이때 2의 배수는 통과한다.)
• 위와 같은 방식으로 주어진 정수 N의 제곱근까지 반복한다.
  • 소수는 1과 자기 자신으로만 나눠져야 한다. 즉, 약수로 1과 자기 자신만 있다는 말이다.
  • 예를 들어, 8의 약수는 1, 2, 4, 8이다.
  • 이때 8의 제곱근 2√2의 정수는 2이다. 따라서 자기 자신의 제곱근이 초과되는 숫자가 약수가 되지는 않는다.
  • (4는 2를 약수로 가지고 있다.)
• 제외되지 않은 수를 확인하면 2부터 주어진 정수 N 사이의 약수를 알 수 있다.

 

따라서 이번 문제는 에라토스테네스의 체 알고리즘을 사용하여 풀어보자.

Answer

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) {
        int M = 0;
        int N = 0;

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            M = Integer.parseInt(br.readLine());
            N = Integer.parseInt(br.readLine());
        } catch (IOException e) {
            System.err.println("ERROR = " + e.getMessage());
        }

        boolean[] nonPrimeNumbersCheck = getNonPrimeNumbersCheck(N);
        int primeNumberSum = 0;
        int primeNumberMin = -1;

        for (int i = M; i <= N; i++) {
            if (!nonPrimeNumbersCheck[i]) {
                if (primeNumberMin == -1) {
                    primeNumberMin = i;
                }
                primeNumberSum += i;
            }
        }

        StringBuilder sb = new StringBuilder();
        if (primeNumberMin != -1) {
            sb.append(primeNumberSum);
            sb.append("\n");
        }
        sb.append(primeNumberMin);

        System.out.print(sb);
    }

    static boolean[] getNonPrimeNumbersCheck(int N) {
        boolean[] nonPrimeNumbersCheck = new boolean[N + 1];

        nonPrimeNumbersCheck[0] = true;
        nonPrimeNumbersCheck[1] = true;
        for (int i = 2; i < Math.sqrt(N); i++) {
            if (nonPrimeNumbersCheck[i]) {
                continue;
            }

            for (int j = i * i; j <= N; j += i) {
                nonPrimeNumbersCheck[j] = true;
            }
        }

        return nonPrimeNumbersCheck;
    }
}

 

Code Review

try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
    M = Integer.parseInt(br.readLine());
    N = Integer.parseInt(br.readLine());
} catch (IOException e) {
    System.err.println("ERROR = " + e.getMessage());
}

`try-with-resources`로 try에 객체의 자원을 받아서 try문이 끝나면 `br.close()`를 하지 않아도 자동으로 자원을 반환한다.

`System.in`으로 사용자로부터 입력받은 데이터를 바이트 스트림으로 받는다.

`InputStreamReader` 클래스로 바이트 스트림을 문자 기반 스트림으로 변환한다.

`BufferedReader` 클래스로 문자 스트림을 읽는다.

 

문자열 한 행을 `br.readList()`으로 읽어서 `Integer.parseInt()`로 정수 변환 후 각각 미리 선언된 M, N에 대입한다.

 

static boolean[] getNonPrimeNumbersCheck(int N) {
    boolean[] nonPrimeNumbersCheck = new boolean[N + 1];

    nonPrimeNumbersCheck[0] = true;
    nonPrimeNumbersCheck[1] = true;
    for (int i = 2; i < Math.sqrt(N); i++) {
        if (nonPrimeNumbersCheck[i]) {
            continue;
        }

        for (int j = i * i; j <= N; j += i) {
            nonPrimeNumbersCheck[j] = true;
        }
    }

    return nonPrimeNumbersCheck;
}

N까지의 자연수를 파라미터로 받아 소수가 아닌 숫자 배열을 반환하는 `getNonPrimeNumbersCheck()` 메서드를 생성한다.

이후에 index로 해당 숫자를 가져오기 쉽게 배열의 크기를 `N + 1`로 하여 boolean배열 `nonPrimeNumbersCheck` 객체를 생성한다. (이제 index를 숫자로 생각해도 된다.)

 

숫자 0과 1은 소수가 될 수 없으므로 true를 대입한다.

 

소수를 판별하기 위해 2부터 N의 제곱근까지 나누기 위한 for문을 만든다.

이 for문을 반복할 때 `nonPrimeNumbersCheck` 배열에서 해당 index의 값이 true이면 `continue`로 for문을 다음으로 통과시킨다.

예를 들어, 현재 i가 4일 때 4는 2의 배수이다. 따라서 아래 로직에서 이미 소수가 아님을 판별했으므로 통과시킨다.

 

i * i부터 주어진 정수 N까지 j + i만큼 증가시켜 반복시키는 for문을 생성한다.

예를 들어, i가 2이고 N이 18이면 4부터 18까지 2씩 증가시키면서 반복한다.

 

말로는 모호하니 위 로직을 N이 18일 경우를 예시로 표를 확인하자.

i	i * i	j += i -> j = j + i
2	4	4
		6
		8
		10
		12
		14
		16
		18
3	9	9
		12
		15
		18

예시 18의 제곱근은 3√2 이므로 i는 2부터 3까지 반복한다.

i * i를 하는 이유는 2와 3은 소수이기 때문이다. 그러면 i가 4일 때는? 이라는 궁금증이 나올 수 있는데 4는 2의 배수라 이미 소수가 아님이 판별되어 있으므로 통과될 것이다.

j += i 씩 2의 배수 판별이 끝났으면 3의 배수 판별을 한다. 이때 2의 배수 판별에서 이미 12, 18이 나와서 조건 처리를 할까 했지만 그렇게 할 경우 조건 확인을 매번 해야 되기 때문에 차라리 배수가 되는 것에만 대입되는 게 나을 것 같다고 생각했다.

 

모든 반복문이 종료되었으면 `nonPrimeNumbersCheck` 배열을 반환한다. 이때 배열에서 false인 index가 소수이다.

즉, 위 표에서 없는 5, 7, 11, 13, 17이 예시 정수 18까지의 소수들이다.

 

boolean[] nonPrimeNumbersCheck = getNonPrimeNumbersCheck(N);
int primeNumberSum = 0;
int primeNumberMin = -1;

for (int i = M; i <= N; i++) {
    if (!nonPrimeNumbersCheck[i]) {
        if (primeNumberMin == -1) {
            primeNumberMin = i;
        }
        primeNumberSum += i;
    }
}

소수가 아닌 수가 true로 판별한 배열을 `nonPrimeNumbersCheck`에 반환받는다.

소수인 수들을 합할 `primeNumberSum`과 소수의 최솟값을 구할 `primeNumberMin`을 선언한다. 이때 소수가 없으면 -1을 출력해야 하기 때문에 최솟값은 -1로 초기화한다.

 

입력받은 M부터 N까지의 소수를 확인하는 for문을 만든다.

`nonPrimeNumbersCheck` 배열에서 false인 수를 찾아서 `primeNumberSum`에 더해준다. 이때 처음 나온 소수를 `primeNumberMin`에 대입한다.

 

StringBuilder sb = new StringBuilder();
if (primeNumberMin != -1) {
    sb.append(primeNumberSum);
    sb.append("\n");
}
sb.append(primeNumberMin);

System.out.print(sb);

출력을 두줄 이상해야 되기 때문에 `StringBuilder` 객체를 생성했다.

소수가 없을 경우가 아니라면 소수합계와 최솟값을 `sb.append()`하여 출력하고,

소수가 없을 경우. 즉, `primeNumberMin`이 -1일 경우라면 -1이 출력되도록 한다.

 

Result

이전에 소수를 구하는 문제에서는 주어진 자연수 하나를 2부터 제곱근까지 구해서 시간복잡도가 O(√N)이었다.

이번에 여러 소수를 구하는 문제에서는 에라토스테네스의 체를 사용해서 2부터 제곱근까지와 각 소수의 배수를 제거해서 시간복잡도가 O(Nlog(logN))으로 이전보다 더 효율적인 것 같다.

하지만 자연수 하나만 소수인지 판별할 때는 이전방법을 사용하는 것이 좋을 것 같다.