소수 찾기 (programmers Lv1)

소수찾기

def solution(n):
    num=set(range(2,n+1))

#1 범위는 왜? 
    for i in range(2,(n**0.5)+1):
        if i in num:

#2 왜 range 함수를 저렇게? range([start], stop[, step])

            num-=set(range(2*i,n+1,i))
    return len(num)

#3 에라토스테네스의 채를 이용? 

소수 찾기는 이중 for 문을 돌려서 답이 나올 수 있지만 효율성 x

__#1 범위는 왜?
이유는 간단하다. 소수 판별에서 2부터 해당 숫자의 제곱근까지의 범위를 사용하는 이유는 간단합니다. 만약 어떤 수 n이 소수가 아니라면, n의 약수는 n의 제곱근보다 작거나 같은 수 중에서 찾아집니다. 결론은 범위를 줄일 수 있습니다.

__#2 range 함수를 왜?
위에 한개만 존재하기에 set을 사용하신건 다들 아실겁니다. for문을 통하여 2부터기에 4부터 시작해서 100까지의 범위에서 2씩증가하는 값을 뺀값이 결국 num의 값에 남는다. 따라서 4부터 2씩 증가한다면 4,6,8,10....그렇게 되면 결국 num의 길이가 n보다 작은 소수의 값만이 존재되어 len함수를 사용하여 return 한다.

__#3 에라토스테네스의 채를 이용?
- 에라토스테네스의 체의 원리는 다음과 같습니다:

1. 2부터 N까지의 모든 수를 나열한다.
2. 현재 나열된 수 중 가장 작은 수를 선택하고, 그 수의 배수들을 모두 제거한다.
3. 남아 있는 수 중 가장 작은 수를 선택하고, 그 수의 배수들을 모두 제거한다.
4. 반복하여 남아 있는 수가 없을 때까지 계속한다.

세가지 내용을 모르는 저는 효율성까지 따지는 방법을 찾아보고 정리하였습니다. 추후 백준 '소수 찾기'문제도 풀어보면서 이해를 다지겠습니다.