[Programmers][Python] 소수 찾기

1. 시간 초과

n 이하의 소수 개수를 찾는 문제이다. n이 1000000 이하의 자연수라 처음 한 방법은 시간초과가 났다.

list를 계속 만들어서 그런가?

def solution(n):
    prime = list(range(2, n + 1))
    for i in range(2, n + 1):
        if i in prime:
            prime = list(filter(lambda x : x % i != 0 or x == i, prime))
    
    return len(prime)
# 시간 초과

2. 정답

bool list를 만들고 에라토스테네스의 체를 이용하여 풀었다.

prime의 i번째 원소가 수 i이고, prime[i]가 true이면 i는 소수이다.

만약 i가 소수라면 j = 2 * i, 3 * i, 4* i ..... <= n인 j에 대해 prime[j]를 false로 바꿔준다. 즉 j는 소수가 아니라고 바꿔준다.

def solution(n):
    prime = [True for _ in range(n + 1)]
    prime[0] = prime[1] = False
    for i in range(2, n + 1):
        if prime[i]:
            j = i
            while j <= n - i:
                j += i
                prime[j] = False
    return sum(prime)