프로그래머스 - 소수 찾기

자세한 설명은 링크 참고

주어진 숫자 내에 소수가 몇개 있는지 알아보는 문제이다.

이 문제는 이전에 '아라토스테네스의 체'라는 공식을 이용하지 않으면 효율성에서 탈락했기 때문에 얄미워서 안풀려고 생각했었다. 하지만 얄미워도 지식은 쌓아야 한다.
참고 : 아라토스테네스의 체

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # 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, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

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

참고내에 코드가 있지만 가져와봤다.
개념은 소수 2에 배수는 모두 소수가 아니기 때문에 제거해주면 되는 형식으로 모든 소수의 배수를 제외하는 코드라고 생각하면 될 것 같다.
이것을 구현하면 이렇다.

def solution(n) :
    m = set(range(2, n+1))
    for i in range(2, n+1) :
        if i in m :
            m -= set(range(i+i, n+1, i))
    return len(m)

사실 이 코드가 나오기까지 어마어마한 시간이 걸렸다.
효율성에서 통과하지 못하여 아예 초기화하고 코드를 새로 짜는 걸 3번정도 한것 같다.
그래서 결과는

효율성을 생각해보자.