[프로그래머스] 소수 찾기- level1

프로그래머스 문제 중 "소수 찾기"라는 문제를 푸는데

이렇게 풀었더니 몇몇 테스트케이스에서 오류초과가 났다.

구글링을 했더니 "에라토스테네스의 체" 라는 방법을 알게 되었다.

 

"에라토스테네스의 체" 란?

범위에서 합성수를 지우는 방식으로 소수를 찾는 방법. 1. 1은 제거 2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다. 3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다. 4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다. 5. (반복)

 

 

답

def solution(n):
    answer = set(range(2,n+1))
    
    for i in range(2,n+1):
        if i in answer:
            answer -= set(range(i*2,n+1,i))
    return len(answer)

 

answer에 set()으로 2~n까지 저장하고

2~n까지 answer에 i가 있다면 i의 배수를 모두 제거한다.

그러면 2~n까지의 소수만 answer에 남아있게 된다.

answer의 개수는 len()사용해서 표현!!