소수 찾기(feat. 에라토스테네스의 체)

알고리즘 문제에서 소수를 찾으려는데 시간 복잡도에서 걸렸다.
처음 사용한 소수찾는 함수는 다음과 같다.

def get_sosu(num):
    if num == 1:
        return 0

    for i in range(2, num):
        if num % i == 0:
            return 0
    return 1

• 소수는 1과 자기 자신을 제외한 숫자 외에는 약수가 될 수 없다.
• 다음과 같은 코드를 통해 2에서부터 자기 자신까지 모두 나눴을 때 나머지가 0이 되면 소수가 아니며, 0이 한번도 나오지 않는다면 소수이다. (완전탐색 방법이다. 시간복잡도는 슬퍼지겠다)
• 시간복잡도는 O(n) 이 되려나..

아무튼 구하려는 숫자가 커질 수록 시간이 그만큼 늘어나게 되므로 비효율적이다.
소수를 찾는데 가장 효율적인 알고리즘은 에라토스테네스의 체 이다.

 

 

 

파이썬으로 구현한 에라토스테네스의 체는 다음과 같다.

def get_prime_num(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * (n + 1)
 
		# n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n + 1, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False
 
    # 소수 목록 산출
    return [i for i in range(2, n + 1) if sieve[i] == True]

- 시간 복잡도는 O(NloglogN)

- 하지만 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요하다. 

  - 10억이 소수인지 아닌지 판별해야 할 때 에라토스테네스의 체는 사용하기 좋지 않을 수도 있다.

 

 

 

 

참고

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

https://www.youtube.com/watch?v=9rLFFKmKzno