:orphan:

Count Primes
============

.. highlight:: none

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

Given an integer ``n``, return *the number of prime numbers that are
strictly less than* ``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``\ :sup:```6```

.. highlight:: python

Pattern
-------
Array, Math, Enumeration, Number Theory

Solution
--------
Use the Sieve of Eratosthenes. Ordinarily, we would start with a list of
integers ``primes = list(range(2, n))`` and remove multiples of ``primes[0]``
(2), then the multiples of ``primes[1]`` (3), and so on. However, this was too
slow for leetcode. Instead, we track whether each number ``i`` is prime in a
list of ``bool``s ``is_prime``. We mark the multiples of ``i`` as not prime by
setting ``is_prime[c * i] = False`` for :math:`c > 2`. The number of primes is
the number of ``True``.

Code
----

.. literalinclude:: ../problems/medium/count-primes/count_primes__approach_1.py
    :language: python
    :lines: 12-

Test
----
>>> from count_primes__approach_1 import countPrimes
>>> countPrimes(10)
4
>>> countPrimes(0)
0
>>> countPrimes(1)
0

Complexity
----------
| Time: :math:`O(n \log \log n)` — Sieve of Eratosthenes
| Space: :math:`O(n)` — boolean sieve array

.. autofunction:: count_primes__approach_1.countPrimes