[Level1] 소수찾기

문제 

입력받은 N까지의 수 중 소수의 개수를 출력한다.

 

입력

10

 

출력

4

---

처음에 for문을 이용해서 소수를 구했을 때 시간초과가 발생했다. 

따라서 에라토스테네스의 체를 이용해서 푸는 방법을 알게되었다. 원리는 다음과 같다.

1~50까지의 수 중 소수를 구하려고한다.

1. 1은 소수가 아니니 제외시키고 2부터 구한다.

2. 2는 소수이고 2의 배수들을 소수가 아니라고 판단하고 걸러낸다.

3. 걸러내고 남은 수 중 가장 작은 수인 3은 소수이고 또 3의 배수들을 걸러낸다.

4. 걸러내고 남은 수 중 가장 작은 수인 5는 소수이고 또 5의 배수들을 걸러낸다.

5. 위의 과정을 반복하면 소수만 남게되고 소수를 출력하면된다.

 

python

- primbe_number에 set형태로 2부터 n까지의 수를 생성했다.

- 2부터 n까지 for문을 돌려 i가 prime_number에 있으면 i를 제외한 i의 배수를 set형태로 만든다.

- 위에서 만든 set을 prime_number와 차집합을 해주면 걸러지게된다.

- 위의 과정을 반복하면 된다. 

def solution(n):
    prime_number=set(range(2,n+1))
    
    for i in range(2,n+1):
        if i in prime_number:
            prime_number-=set(range(i+i,n+1,i))
    return len(prime_number)