[프로그래머스/Programmers] 소수 찾기_1 - Python

Link

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

 

Solution

해당 문제는 에라토스테네스의 체를 사용하지 않으면 효율성 테스트를 통과할 수 없다.

에라토스테네스의 채는 (int(n ** 0.5) + 1)까지의 수들의 배수들을 지워나가며 소수를 구해내는 방법이다.

def solution(n):
    sieve = [True] * (n + 1)

    m = int(n ** 0.5)

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

    return sieve.count(True) - 2

🔑 key point: 에라토스테네스의 체

 

Other Solution

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)