[프로그래머스] 소수 찾기(with python)

문제

 처음에 이중for문으로 해결하려다 보니 n이 클 때 시간복잡도가 크게 증가하여 시간초과로 통과하지 못했다.

힌트를 얻기 위해 질문하기에 들어가봤다. '에라토스테네스의 체' 라는 개념을 사용해야 한다.

 

 그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수(素數)를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다. [네이버 지식백과] 에라토스테네스의 체 [Eratosthenes' sieve] (두산백과)

에라토스테네스의 체

 

통과한 답 : 

def solution(n):
    l=[False,False]+[True]*(n-1)
    primes=[]
    for i in range(2,n+1):
        if l[i]:
            primes.append(i)
            for j in range(2*i,n+1,i): #i씩 건너가면서 배수들을 삭제
                l[j] = False
    return len(primes)

 

다른 사람의 풀이 : 

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)

👏🏻👏🏻👏🏻