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

https://school.programmers.co.kr/learn/courses/30/lessons/12921

연습문제

def solution(n):
    answer = 0
    for i in range(2, n+1):
        count = 0
        for j in range(i, 1, -1):
            if i % j == 0:
                count += 1
        if count == 1:
            answer += 1
    return answer

처음 짠 코드인데 효율성 테스트에서 시간초과 발생

def solution(n):
    prime_number = [False, False] + [True for i in range(n-1)]
    for idx, val in enumerate(prime_number):
        if val:
            for i in range(idx*2, n+1, idx):
                prime_number[i] = False
    return sum(prime_number)

에라토스테네스의 체를 사용해서 다시 구현해서 해결

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)

for문 대신 set()을 써서 배수들을 한 번에 제거했음