[LeetCode 풀이/python] 204. Count Primes (easy)

문제 설명: 0 이상의 숫자 n 보다 작은 수 중 소수(prime number) 의 개수를 리턴하시오.

 

(Count the number of prime numbers less than a non-negative number, n.)

 

 

예시 1)

입력: n = 10  -->  출력: 4

설명: 10 보다 작은 소수는 2, 3, 5, 7 의 4개가 존재함

 

예시 2)

입력: n = 0  -->  출력: 0

 

예시 3)

입력: n = 1  -->  출력: 0

 

제한 조건:

• 0 <= n <= 5*10^6

 

------ * ------ * ------ * ------

 

[풀이 1안]  (w/solution peeping)

• 접근법
  • 주어진 n 보다 작은 소수 값을 모두 리턴할 필요 없이 개수만 세면 되므로,  0 이상 ~ n 미만의 각 정수를 인덱스로 갖는 크기 n 인 memoization 테이블을 만들어 각 정수가 소수인지를 boolean (True/ False) 로 저장
  • n 이 소수인 경우, 해당 n 을 제외한 i 의 k 배수 (k*i <=n) 에 대해 합성수(not 소수) 로 처리해 줌
  • for loop 문의 범위를 n 이 아닌 sqrt(n) + 1 까지로 제한하는 이유는, n = a * b 로 표현할 때 a > sqrt(n) 인 경우 해당 a 는 이미 a < sqrt(n) 인 관계에서 b 로서 등장했을 것이기 때문...! (a < sqrt(n) 인 a 를 처리하는 과정에서 처리됨~)
  • 한편 k*i 를 False 로 체크하는 과정의 for loop 문에서 i*i 부터 시작하는 이유는 k < i 인 경우에 대해서는 이미 더 작은 i 를 처리하는 과정에서 처리되었을 것이기 때문...!

 

• 코드 구현

def countPrimes(n: int) -> int:
    dp = [True] * n
    if n < 2: return 0
        
    for i in range(int(n ** 0.5) + 1):
        if i < 2:
            dp[i] = False
        elif dp[i]:
            for j in range(i*i, n, i):
                dp[j] = False
    return sum(dp)
    

 

• 결론
  • 찾아보니 소수 구하는 알고리즘의 정석인 듯 하다... 잘 기억해둬야지 ~) 0ㅅ0)~
  • 시간 복잡도는 sqrt(n)...!