[LeetCode | Python] 204. Count Primes

느낀점

오래전 프로그래머스에서 풀었던 "에라토스테네스의 체"를 다시 한번 보게 되었다.

 

문제

https://leetcode.com/problems/count-primes/ 

특정 숫자 직전까지의 소수 갯수 찾기

풀이

갯수 만큼 배열을 생성한 이후, 소수를 발견할 때마다 그의 배수들에 접근하지 못하도록 막는다. 또한, 바깥쪽 루프에서 i가 소수일 때만 안쪽 루프가 실행되기 때문에 단순 소수 판별 알고리즘 보다는 빠르다.

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 2:
            return 0 

        h = [True] * n
        h[0], h[1] = False, False

        cnt = 0
        for i in range(2, n):
            if h[i]:
                cnt += 1
                for j in range(i*i, n, i):
                    h[j] = False
        
        return cnt

 

결과

• 공간복잡도: $$ O(NLogLogN) $$
• 시간복잡도: $$ O(N) $$