풀이_LC204.md

🍕 LeetCode 204. Count Primes

• Date : 2021.08.22(일)
• Time : 20분

Problem

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

Constraints

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

Example

• Input: n = 10
• Output: 4
• Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

풀이

def countPrimes(self, n: int) -> int:

    def getPrime(n):
      primes = [True] * n
      m = int(n ** 0.5)
      for i in range(2, m+1):
          if primes[i] == True:
              for j in range(i+i, n, i):
                  primes[j] = False
      return [i for i in range(2,n) if primes[i] == True]

    primeListn = getPrime(n)
    return len(primeListn)

: 이 문제는 소수를 찾는 문제이다. 소수를 찾는 방법에는 크게 2가지가 있는데, 완전 탐색을 이용하는 방법과 에라토스테네스의 체를 이용하는 방법이 있다. getPrime(n)이라는 함수를 만들어서 에라토스테네스의 체의 방법을 이용해보았다. 먼저 모든 구간의 수를 소수라고 판단해둔다 -> True로 설정한다. 이 구간은 0부터 시작되어서 n-1 까지 진행된다. for 문의 구간은 n의 제곱근까지 진행한다. 자기 자신은 제외하기 때문에 i+i 를 시작으로 잡고 계속 그 수의 배수만큼 늘려주면서 False 값으로 바꿔준다. 이제 True 인 값은 소수이기 때문에 소수인 인덱스 값만 배열에 저장해서 return 해준다. 이 문제에서는 소수의 개수를 return 하면 되기 때문에 배열의 길이를 return에서 답을 구해주었다.