programmers | Lv1. 소수 찾기 [Python]

💡 Python 3

🔗 문제

소수 찾기 [Link]

💻 코드

소수 찾는 방법.. 효율성 테스트에서 n번 실패 후,, 효율적으로 풀 수 있는 방법을 찾아보았다.
다들 에라토스테네스의 체를 사용하네.. 오늘도 하나 더 배웠다 !!

# 에라토스테네스의 체 
def solution(n):
    import math
    prime_list = [True] * (n+1) # True 면 소수
    k = math.ceil(math.sqrt(n)) # n의 최대 약수 sqrt(n)
    for i in range(2, k + 1):
        if prime_list[i]:
            for j in range(i+i, n+1, i):
                prime_list[j] = False # i의 배수 모두 false로 바꾸기
                
    return prime_list.count(True) -2 # 0, 1에 해당하는 인덱스 제외

💥 다른 사람 코드

set을 이렇게 활용할 수 있구나..
n이 커질수록 속도 차이가 있겠지만 훨씬 간결하다..

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)

참고 자료

[Algorithm] 에라토스테네스의 체
[python]소수 찾기 - 에라토스테네스의 체
[Python] 반올림, 올림, 내림
[Python] 소수 구하기 (에라토스테네스의 체)