[leetcode 204] Count Primes

204. Count Primes

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

해결 과정

처음엔 단순히 주어진 n 미만까지, 그리고 본인까지 2중 for 문을 돌면서 나누어 떨어지지 않으면 prime 으로 판단하도록 하였는데, 큰 수에서 Time Limit Exceeded 에러가 발생했다.

방법을 찾다가 에라토스테네스의 체 를 알게 되어, 에라토스테네스의 체를 활용하여 풀었다.

코드

fun countPrimes(n: Int): Int {
    val notPrime = BooleanArray(n+1)
        
    for(i in 2 until n) {
        if(!notPrime[i]) {
            var j = i * 2
            while(j <= n) {
                notPrime[j] = true
                j+=i
            }
        }
    }
        
    var result = 0
    for(i in 2 until n) {
        if(!notPrime[i]) {
            result ++
        }
    }
    return result
}

배운 점

• 에라토스테네서의 체
  • 주어진 수까지의 모든 소수를 구할 때 좋은 방법.
  • 2의 배수를 모두 지우고, 3의 배수를 모두 지우고.. 이런식으로 소수의 배수들을 지우면서 남는 숫자들을 소수로 판단할 수 있다.