[python] 소수 찾기

 

def solution(n):
    # 소수로 간주 n개 True
    sieve = [True] * (n+1)
    # n의 최대 약수 sqrt(n) -> i=sqrt(n)까지 for문
    m = int(n **0.5)
    for i in range(2, m+1):
        if sieve[i] == True: # i가 소수인 경우
            for j in range(i+i,n+1,i): # i이후 i의 배수들 False 판정
                sieve[j] = False
                
    
    return len([i for i in range(2, n+1) if sieve[i] == True])