[프로그래머스] 소수 찾기 (파이썬)

 

https://programmers.co.kr/learn/courses/30/lessons/12921

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

 

 

---

 

 

<나의 풀이>

def solution(n):
    answer = 0
    
    #소수인지 체크하는 리스트 : 0과 1은 소수가 아니므로 처음부터 False로 한다.
    check_list = [False,False] + [True]*(n-1)
    
    # 소수의 배수는 소수가 아니라는 것을 이용해 소수의 배수는 False 처리 해준다.
    for i in range(2,n+1) :
        if check_list[i] :
            answer += 1
            for j in range(2*i,n+1,i):
                check_list[j] = False
    return answer

 

에라토스테네스의 체로 구한 소수찾기 코드

 

 

<다른 사람의 풀이>

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)
    
# <배운점> 
# => 에라토스테네스의 체를 더 간결하게 표현한 것