프로그래머스 소수찾기(파이썬)

에라토스테네스의 체를 이용하는 문제. 모든 수를 소수라 하고 소수를 1로 a배열에 저장해두고

소수의 배수들은 모두 소수가 아니다라는 개념을 이용한 dp.

소수를 1로 둬서 소수의 개수를 찾기도 쉽다. 

def solution(n):
    answer = 0
    a=[1]*(n+1)        # 소수면 1
    a[0]=0
    a[1]=0
    for i in range(2,n+1):
        if a[i]==0:
            continue
        for j in range(2,n//i+1):
            a[i*j]=0
             
    answer = sum(a)     #소수 개수의 총합
        
    return answer