문제

https://programmers.co.kr/learn/courses/30/lessons/12921

나의 코드

"""
1. 아이디어
제한 사항에 적힌 "n은 2이상 1000000이하의 자연수입니다." 이건 절대로 소수를 쉽게 구할 수 있을때 나오는 O(n^2) 코드를 쓰지 말라는 거다.
에라토스테네스의 체를 이용해서 구현해야 한다.

2. 시간복잡도
O(NloglogN) 이라고 한다..
"""

def solution(n):

    chk = [True] * (n+1)
    
    m = int(n ** (0.5))
    
    for i in range(2, m+1):
        
        if chk[i] == True:
            for j in range(i*i, n+1, i):
                chk[j] = False
    
    x = [i for i in range(2, n+1) if chk[i] == True]

    return len(x)
    

느낀점

에라토스테네스의 체 이론은 쉽지만 막상 구현할려면 헷갈리니깐 이렇게 기록해놓았다가 써야할 때 보면서 구현해야 한다.