[Algorithm] 에라토스테네스의 체

대량의 범위에서 빠르게 소수를 판별할 수 있는 '에라토스테네스의 체'에 대해 정리합니다.

1. 소수를 판별할 범위만큼 할당
2. 2부터 시작하여 어떤 수가 할당한 set에 있는지 확인 후,
   있으면 그 수의 배수(2 * 특정 수)를 지웁니다.
   (자기 자신은 지우지 않습니다)

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)

위의 코드는 1부터 n까지의 범위에서 소수가 몇개인지 에라토스테네스의 체 알고리즘을 사용하여 풀이한 코드입니다.