[백준] 1929번: 소수 구하기 (java, python)

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

1929번: 소수 구하기

---

💡주의 사항

알고리즘 분류에 에라토스테네스의 체가 있음을 알아두자.

우리가 흔히 아는 소수 판정으로 문제를 풀었다면, 필자처럼 가차없이 시간초과를 겪을 것이다.

---

 🗒 풀이

java

1) 시간 초과

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

public class Fail {
    public static boolean isPrimeNumber(int num) {
        for (int i = 2; i < num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    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());
        for (int i = M; i <= N; i++) {
            if (isPrimeNumber(i)) {
                System.out.println(i);
            }
        }
    }
}

일단 첫번째 코드는 아무 생각없이 우리가 흔히 아는 소수 판별법을 사용했다.

코드를 보면 알겠지만, 2이상 N 미만의 수 중 나누어 떨어지는 수가 존재하는 경우는 소수가 아님을 활용했다.

위의 코드는 이 매커니즘을 사용하여 2부터 N까지 이 매커니즘을 N번 반복하는 것을 볼 수 있다. 시간 복잡도는 $O(N^2)$.

처음에는 Scanner를 사용했지만, 시간 초과가 떠서 아무 생각없이 '아 input에서 오래 걸리나?'라는 단순하고 멍청한 착각을 해 BufferedReader로 바꾸어주었지만, 역시나 시간초과로 당황했음을 볼 수 있다.

 

---

2) 에라토스테네스의 체

알고리즘 분류를 보니 처음 보는 것이 있었다.

바로 '에라토스테네스의 체'이다. 구글링을 바로 해봤다.

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

에라토스테네스의 체는 고대 그리스의 수학자 에라토스테네스가 만든 소수를 찾는 방법으로, 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다고 한다.

에라토스테네스의 체는 제곱근을 이용하는 것이다.

만약 $1$과 $N$이 자신이 아닌 두 수 $a, b$의 곱으로 되어 있다고 생각해보자. 이 때 N은 소수가 아니다.

$N = a * b$이고, $N'$은 $N$의 제곱근이다.

여기서 만약 $a >= N'$이라면, $a * b = N = N' * N'$이고 $b <= N'$라고 한다.

때문에 N의 제곱근까지만 검사를 해도 충분히 소수인지 합성수인지 판별할 수 있다는 것이 에라토스테네스의 체의 근간이다.

 

이것은 임의의 자연수 $N$에 대하여 그 이하의 소수를 찾는 가장 간단하고 빠른 방법이라고 한다.

순서는 다음과 같다.

출처 - https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

1. 일단 1부터 구하고자 하는 구간의 모든 수를 나열한다.

2. 소수도, 합성수도 아닌 유일한 자연수 1을 제거한다.

3. 2는 소수이므로 2는 포함한다.

4. N을 제외한 2의 배수를 모두 지운다.

5. 3은 소수이므로 3도 포함한다. N을 제외한 3의 배수를 모두 지운다.

6. 남은 수 중 5는 소수이므로 5도 소수에 포함시킨 후 N을 제외한 5의 배수를 모두 지운다.

7. 남은 수 중 7도 소수이므로 소수에 포함시킨 후 N을 제외한 7의 배수를 모두 지운다.

8. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

이 때, 제곱근을 이용해야한다고 했다. 위의 그림처럼 120까지의 소수를 구한다고 한다면, $11^2 > 120$ 이므로, 11보다 작은 수의 배수들만 지워도 충분하다. 이런 식으로 소수를 구하면 1부터 120까지 각 숫자를 돌면서 소수인지 합성수인지 판별하지 않아도 된다.

 

---

이 개념을 이용해서 코드를 짠다.

위의 링크에 에라토스테네스의 체를 java와 python으로 구현한 코드가 있어 참고하여 코드를 정리했다.

 

import java.util.Scanner;

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

        if (N <= 1)
            return;

        boolean[] primeList = new boolean[N + 1]; // false로 초기화됨
        primeList[0] = primeList[1] = true; // true = 소수 아님, false = 소수

        for (int i = 2; i <= Math.sqrt(primeList.length); i++) {
            if (primeList[i]) continue;
            for (int j = i * i; j < primeList.length; j += i) {
                primeList[j] = true;
            }
        }

        for (int i = M; i <= N; i++) {
            if (!primeList[i]) {  // false가 소수이므로 소수 출력
                System.out.println(i);
            }
        }
    }
}

M과 N을 입력받고, N이 1보다 작으면 말이 안되므로 종료시킨다.

소수인지, 아닌지 판별하기 위해 boolean 배열을 생성한다. 이 때 초기화는 false로 되어있기 때문에, 편리하게 하기 위하여 true를 합성수, false를 소수로 지정한다.

for문을 돌며, 제곱근만큼 돌고, 만약 배열에 true값이 있으면 건들지 않고 넘어간다. (continue)

만약 false로 되어 있다면, 해당 문자열이 소수인지 아닌지 판별한다.

마지막엔 false로 되어있는 요소들만 출력한다.

 

---

python

import math
import sys


def is_prime(num):
    if num == 1:
        return False

    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True


M, N = map(int, sys.stdin.readline().split())  # 시간 단축을 위해 input() 대신 sys.stdin.readline() 사용

for i in range(M, N+1):
    if is_prime(i):
        print(i)

자바와 같은 매커니즘으로 짰다.

range를 잘못줘서 첫 번째 시도는 틀렸지만, range 수정 후에 정답인 것을 볼 수 있다.

시간 단축을 위해 input()이 아닌 sys.stdin.readline()을 사용했다.

---