[파이썬🐍] 프로그래머스 : 소수 찾기

 

 

 

def solution(n):
    answer = 0
    for i in range(2,n+1):
        for j in range(2,i):
            if i % j == 0: break
        else: answer += 1
    return answer

<내 풀이(실패)>  

 

시간초과로 실패가 떴다.

 

도저히 방법이 생각이 나지 않아서 서치를 하던 중 

"에라토스테네스의 체" 라는 것을 통해 풀이한 코드를 보게 되었다.

에라토스테네스의 체는 에라토스테네스라는 수학자가 발견한 소수 찾는 방법이다. 

 

 

 

 

기본적인 개념을 설명하자면,,,,

1. num에 n까지의 모든 수를 넣어준다.

2. 에라토스테네스 체 이용(2의 배수,3의 배수,4의 배수, 쭉쭉 n의 배수전까지 구해서 num에서 빼준다.)

3. num의 길이를 계산해주면 끝(소수만 남음)

 

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)

<에라토스테네스의 체를 이용한 풀이(성공)>