에라토스테네스의 체 (python 기본 구현)

def prime_list(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:
            for j in range(i+i, n+1, i): # i 배수는 소수 목록에서 제거(False)
                sieve[j] = False

    return [i for i in range(2, n+1) if sieve[i]]

print(prime_list(20))
# [2, 3, 5, 7, 11, 13, 17, 19]

- 관련 문제 참고:
  - 문제: programmers.co.kr/learn/courses/30/lessons/12921 
  - 풀이: bky373.tistory.com/158

- 출처: 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