에라토스테네스의 체를 이용하는 문제. 모든 수를 소수라 하고 소수를 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