프로그래머스 - 소수찾기

숫자 n을 입력받고 1부터 n까지의 소수의 개수를 찾는 문제이다. (n의 범위 2이상 1000000이하)

완전 탐색으로 모든 숫자를 소수인지 확인하는 쉬운 방법이 있지만, 효율성에서 안된다.

검색을 통해 알아보니 에라토스테네스의 체가 가장 간단한 소수찾는 방법이라고 한다.

---

1부터 n까지 소수 본인을 제외한 소수의 배수를 소거해주는 방법인데,

가장 빠른 이유는 제곱한 수가 n을 넘어가는 수까지의 소수만을 확인하면 되기 때문이다.

 

예를 들면 n이 120이라고 가정했을 때, 11의 제곱은 121이므로 11보다 작은 소수의 배수만 지우면 된다.

 

11보다 작은 소수는 2,3,5,7이므로 이를 제외한 소수들의 배수를 소거해주면 된다.

 

처음에 생각한것은 숫자가 소수인지 확인하고 소수이면 answer+=1를 해준 뒤, primelist에 추가한다.

이후, 검증하는 수마다 primelist의 배수에 해당하는지를 확인하는 알고리즘을 짰는데....

 

효율성 조건에 부합하지 못한다.

 

그래서 스터디원에 도움을 받아서 짰다.

 

 

def solution(n):
    
    answer = 0
    prime = [False]*(n+1)
    m = int(n**0.5)
    for i in range(2,m+1):
        if prime[i] == False:
            for j in range(i+i,n+1,i):    
                prime[j] = True
    
    
    answer = prime.count(False)-2