[프로그래머스](python) 소수 찾기

문제

🧩 수도 코드

1부터 n의 sqrt2까지 소수인지 탐색 후 소수 리스트를 만들어 길이 반환

🏁 내 풀이

def solution(n):
    nlist = [True] * (n+1)
    m = int(n**0.5)
    for i in range(2,m+1):
        if nlist[i] == True:
            for j in range(i+i,n+1,i):
                nlist[j] == False
    return len([i for i in range(2,n+1) if nlist[i] == True])

📌 참고 - 에라토스테네스의 체

🧩 다른 풀이

def solution(n):
    num=set(range(2,n+1))

    for i in range(2,n+1):
        if i in num:
            num-=set(range(2*i,n+1,i))
    return len(num)

• range(2,n+1) 중복 없는 리스트 num 생성
• range(2,n+1)에서 i가 num에 있으면:
  num에서 set(range(2*i,n+1,i)) 제거
• num의 길이(수) 반환

에라토스테네스의 체를 사용한 점에서 같은 알고리즘!
시간복잡도는 이 코드가 더 높을 것 같다.