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

 

 

백준 4948번을 푸는데 또 계속 시간초과가 떠서

결국 백준에서 질문을 검색해봤는데,

'에라토스테네스의 체'에 대해 공부해보라는 답글을 발견했다.

 

그래서 '에라토스테네스의 체'에 대해서 한번 알아봤다.

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

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

 

 

'에라토스테네스의 체'는 에라토스테네스(Eratosthenes)라는 수학자가 찾은, 소수 찾는 방법이라고 한다.

가장 작은 소수(2)를 하나 찾으면 그 소수의 배수들을 전부 제외시킴.

→ 남은 것들 중 가장 작은 소수 하나(3)를 또 찾아서 그 소수의 배수들을 전부 제외.

→ 이런 식으로 계속 반복...

 

 

직접 코딩을 해보려고 했는데, 뭔가 생각만큼 부드러운(?) 코딩이 되지 않았다..ㅠㅠㅠ

위키백과에 올라와 있는 코드를 보니,

나는 소수가 아니면 리스트에서 remove하는 방식으로 코딩을 짰는데

위키에 있는 코드는 소수면 True, 아니면 False로 설정하는 방식으로 코딩을 했다.

전체 리스트의 크기나 인덱스를 건드리지 않는 위키의 방식이 더 좋은 것 같다.

아래는 위키에 있는 코드를 거의 그대로 가져온 것이다.

 

 

# n 미만의 소수 찾기.(에라토스테네스의 체)
def primeList(n):
    # 초기화: n개 요소에 True 설정(소수로 간주)
    ans = [True] * n

    for i in range(2, int(n ** 0.5) + 1):
        if ans[i] == True:             # i가 소수인 경우
            for j in range(2*i, n, i): # i를 제외한 i의 배수들을 False 판정
                ans[j] = False

                
    # 소수 목록 추출.
    return [i for i in range(2, n) if ans[i] == True]

prime_list(13)   # 답: [2, 3, 5, 7, 11]  13미만의 소수이므로 13은 포함x.