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

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

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

---

풀이 과정

일정 범위에 있는 모든 소수를 찾아야 하는 문제이다. 1부터 n까지의 수에 대해 모두 소수 판정을 하면서 개수를 세면 답이야 구해지겠지만 시간복잡도가 O(NrootN)인 방법이 되어 효율성 테스트를 통과할 수가 없다.

 

일정 범위에 있는 모든 소수를 찾아야 할 때는 에라토스테네스의 체를 사용하는게 효과적이다. 에라토스테네스의 체가 무엇인지 모르면 아래 위키백과를 참조하면 좋다.

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

에라토스테네스의 체의 시간복잡도는 O(NloglogN)으로 더 효율적이다 N이 100만이라 할때 일일이 소수 판정을 하면 연산 횟수가 약 10억번 언저리까지 나올 수 있지만 에라토스테네스의 체로는 2천만번 언저리의 연산으로 해결이 가능하다.

 

---

소스 코드

def solution(n):
    answer = 0
    check = [False for _ in range(1000001)]
    prime = [] 

    for i in range(2, 1000001):
        if not check[i]:
            prime.append(i)
            for j in range(2*i, 1000001, i):
                check[j] = True

    for prime_number in prime:
        if prime_number > n:
            break
        else:
            answer += 1

    return answer