[Python] 소수 찾기

def solution(n):
    
    number = [False, False] + [True] * n
    answer = []
    
    for i in range(2, n+1) :
        if number[i] :
            answer.append(i)
            for j in range(2*i, n+1, i) :
                number[j] = False
                
    return len(answer)

---

풀이

★ 에라스토테네스의 체를 활용해야 효율성테스트를 통과할 수 있다. ★

 

2021.06.18 - [Algorithm/개념] - 에라토스테네스의 체(Eratosthenes' sieve )

에라토스테네스의 체(Eratosthenes' sieve )

---

참고할만한 풀이

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)

set을 활용하여 차집합으로 문제를 해결하였다.