(LeetCode) 204. Count Primes

204. Count Primes

• Explore : Interview > Top Interveiw Questions > Easy Collection
• 분류 : Math
• 난이도 : Easy

Problem

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

Example 1

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

Example 2

Input: n = 0
Output: 0

Example 3

Input: n = 1
Output: 0

Constraints

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

Solution

Exapnder

class Solution {
    fun countPrimes(n: Int): Int {
        if (n <= 2) return 0
        if (n <= 3) return 1
        if (n <= 5) return 2

        var prime = BooleanArray(n + 1) { true }

        var index = 2
        var number = index * index
        while (number <= n) {
            if (prime[index]) {
                for (i in number .. n step index) {
                    prime[i] = false
                }
            }
            index++
        }

        var count = 0
        for (i in 2 until n) {
            if (prime[i]) {
                count++
            }
        }
        return count
    }
}

Point of Thinking

• 문제 조건대로만 if문으로 분기하면 Accepted.