<p>Given an integer <code>n</code>, return <em>the number of prime numbers that are strictly less than</em> <code>n</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 0
<strong>Output:</strong> 0
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= n &lt;= 5 * 10<sup>6</sup></code></li>
</ul>

import pytest


class Solution:
    def countPrimes(self, n: int) -> int:
        return self.countPrimes_dp(n)

    @staticmethod
    def countPrimes_dp(n: int) -> int:
        if n <=1:
            return 0
        # 1 is true, 0 is false
        primes = [1] * n
        primes[0] = 0
        primes[1] = 0

        for i in range(2,n):
            j = i
            if primes[i]:
                j+=i
                while j < n:
                    primes[j] = 0
                    j += i

        return sum(primes)
    @staticmethod
    def countPrimes_naive(n: int) -> int:
        primes = set()

        def _is_prime(num):
            # even
            if num & 1 == 0:
                return False
            if not primes:
                primes.add(num)
                return True
            else:
                for prime in primes:
                    if num % prime == 0:
                        return False
                primes.add(num)
                return True

        if n <= 2:
            return 0
        num_primes = 1

        for i in range(3, n):
            if _is_prime(i):
                num_primes += 1
        return num_primes


@pytest.mark.parametrize(
    "n,expected",
    [
        (2, 0),
        (499_979, 41537),
        (10, 4),
        (0, 0),
        (1, 0),
    ],
)
def test_countPrimes(n, expected):
    assert Solution().countPrimes(n) == expected

61018