[Python] 소수찾기

 

코딩테스트 연습 - 소수 찾기

특정 범위 내의 소수를 판별하는 문제이다. 블로그의 에라토스테네스의 체의 설명을 보고 온다면 코드 이해가 쉬울 것이다.

에라토스테네스의 체

def sol1(n):
    sieve = [True] * (n+1)
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i]:
            for j in range(i+i, n+1, i):
                sieve[j] = False

    return len([i for i in range(2, n+1) if sieve[i]])

python의 set을 이용하여 더 간결하게 코드를 작성할 수 있다.

 

def sol2(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)​

 

2번째 코드가 보기에는 간결하지만 수행속도, 메모리를 더 많이 소모한다. 아마 set때문이지 않을까 싶다.