[Baekjoon 파이썬] 1929번: 소수 구하기

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

1929번: 소수 구하기

 

문제 설명

숫자 2개를 입력받고 그 숫자의 범위내에 해당하는 소수를 모두 출력하는 문제입니다

ex) 3 10 으로 입력 => 3이상 10이하 내에 있는 소수 모두 출력 => 3,5,7

 

solved.ac에서 티어 실버2 에 분류되어 있는 문제이며 시간 제한은 2초 인것으로 보아 에라토스테네스의 체 알고리즘을 적용시켜야 하는것으로 유추해볼 수 있습니다.

 

Python에서 간단한 소수판별 방법

def check_prime(n):
    if(n == 1):
        return False
    elif (n == 2):
        return True
    else:
        for i in range(2, n):
            if(n % i == 0):
                return False
        return True

소수는 약수가 1과 자기 자신밖에 없는 수 입니다.

이런 정의에 따라 반복문을 이용하여 소수를 판별해볼 수 있습니다.

위는 파이썬으로 구현한 간단한 소수 판별 방법입니다.

 

5의 경우 1, 5 => 약수가 1과 자기자신밖에 없기에 소수 입니다.

 

어짜피 수는 자기 자신과 1을 약수로 무조건 가지기 때문에 숫자 n이 들어오면 2부터 n-1 까지 반복해서 나눠서 나누어떨어지는게 한번이라도 발생하면 그것은 소수가 아니라고 판별해볼 수 있습니다.

 

물론 현재 문제에선 이 알고리즘은 효율성이 조금 떨어집니다.

위 함수는 소수 1개에 대해선 시간복잡도가 $O(N)$ 이 되게 되는데

범위 내의 숫자가 N개에 대해서 판별한다 하면 시간복잡도가 $O(N^2)$이 되게 되고 대부분 시간초과가 뜨게 됩니다.

 

이를 해결하기 위해 범위 내의 소수를 구하는데 효과적인 알고리즘인 에라토스테네스의 체를 적용합니다.

 

에라토스테네스의 체란?

 

* 위 사진은 에라토스테네스의 체를 한눈에 보여주는 gif 입니다.

 

에라토스테네스의 체란 범위 내의 소수를 구할때 간단하지만 강력한 알고리즘 입니다.
방법은 아래와 같습니다.

1. 1은 지우고 2를 소수로 택하고 그 배수를 모두 지워 준다.
2. 그 다음 수인 3을 소수로 택하고 그 배수를 모두 지워 준다.
3. 그 다음 수인 5를 소수로 택하고 그 배수를 모두 지워 준다.
4. 위 테이블이 갱신되지 않을때까지 2,3 과정을 반복해서 시행한다.
5. 남아 있는 것이 소수다.

 

에라토스테네스의 체의 시간복잡도는 $O(Nlog(logN))$ 이며 선형시간과 비슷한 빠른 시간 복잡도를 가지고 있습니다.

왜 시간 복잡도가 이렇게 나오는지는 매우 복잡하기 때문에 본 포스팅에선 다루지 않고 넘어가겠습니다.

범위내의 소수를 빨리 판별가능하단 점으로 받아들이시고 이해하시면 되겠습니다.

 

이것을 소스코드에 적용해보면 아래와 같습니다.

 

소스코드 & 설명

#에라토스테네스의 체
import math

m,n = map(int , input().split())
lst = [i for i in range(m,n+1)]
lst = set(lst) #집합 자료형으로 변환

if 1 in lst:
    lst.remove(1) #1을 제거한다

for i in range(2, int(math.sqrt(n) + 1)):
        #배수를 반복문 돌려서 전부 지워준다.
        j = 2
        while (i * j <= n):
            if i * j in lst:
                lst.remove(i * j)
            j += 1 
            #2x2(j) => 4 .. 2x3(j) => 6 ...
lst = list(lst)
lst.sort()
for item in lst:
    print(item)

우선 숫자 m , n 을 입력받아 그 범위에 있는 모든 숫자를 리스트에 넣어서 만들어 줍니다.

그 다음 그 리스트를 집합자료형으로 변환해줘야 하는데 처음에 set으로 변환을 안해주고 제출하니 시간 초과가 났습니다. 

 

if i * j in lst:
	lst.remove(i * j)

이유는 에라토스테네스의 체를 적용할때 배수를 걸러주는 과정에서 리스트에 그 요소가 있나 없나 확인을 하는게 들어가는데 리스트의 경우 탐색과정에서 시간복잡도 $O(N)$을 가지게 되나 집합자료형 set의 경우엔 데이터의 크기에 상관없이 상수시간 $O(1)$을 가져서 그렇습니다.

 

이유에 관해선 다음을 참고해주세요 : https://rexiann.github.io/2020/11/28/set-in-python.html

 

반복문을 돌릴땐 2부터 제곱근(n)까지 반복하여 그 배수를 지워줍니다. (n은 최댓값)

제곱근(n)까지 반복하는 이유는 1~25의 테이블에서 소수를 모두 구한다면

최댓값 25의 제곱근 5 를 넘어가는 6부턴 지우려고 해도 테이블이 더이상 갱신 되지 않는걸 알 수 있습니다.

(6은 이미 2의 배수를 걸러내는 과정에서 지워졌기 때문)

 

다 지웠다면 마지막에 list로 다시 변환해주고 정렬 과정을 거칩니다.

집합자료형은 순서가 없기 때문에 출력할때 순서가 섞일 수 있는데 이걸 방지하기 위함입니다.

 

이 문제를 풀면서 포인트를 집어보자면

1. 시간복잡도를 줄이기 위해 리스트를 집합자료형으로 바꾼다.
2. 마지막에 꼭 정렬 과정을 거친다.

라고 할 수 있겠네요.

저는 문제를 풀면서 1번을 하지 않아서 처음엔 시간 초과가 나고

2번을 하지 않았을땐 틀렸습니다 를 만났네요.

 

잘 유념하셔서 풀이하시길 바랍니다! 

 

그나저나 메모리가 100mb를 넘어가네요... Test Case에 큰 값을 얼마나 넣어둔거지...

 

아니면 그냥 파이썬이 쓰레기 일수도..?