[Programmers] 소수 찾기

소수 찾기

연습 문제

level 1

 

python3

import math;

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * (n + 1)

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(math.sqrt(n))
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n+1, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False
    

    # 소수 목록 산출
    return [i for i in range(2, n + 1) if sieve[i] == True]

def solution(n):
    return len(prime_list(n))

에라토스테네스의 체를 이용한 방법. (최적화 통과를 위해선 필쑤...)

내용은 대충 2부터 자신을 제외한 배수를 소거(false로 설정)해 나가는 방식. 

true인 애들만 모으면 n 이하의 모든 소수를 얻을 수 있다.

참고로, 위키백과에는 n 미만의 모든 소수를 얻는 코드를 제공하고 있어, n + 1을 해줘야 한다.