# Count Primes

Difficulty: Easy Link: Day 2: May LeetCode Challenge

## Problem Description

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

### Examples

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

## Constraints

• `0 <= n <= 5 * 106`

## Solution

The problem is pretty self evident and is simple to solve but a bit tricky to optimise. A prime number is a number which is only divisible by 1 and itself. You could do Bute-force primality check on numbers between 0 to n whole updating the count. However the complexity would be order of O(N2) and since N is given as the order of 106, so N2 would be bounded by 1012, which would definitely result in TLE (Time limit Exceed error).

### Sieve of Eratosthenes

This is an ancient algorithm for computing prime numbers up to a range and very widely popular in competitive programming (read Sieve of Eratosthenes ). In this algorithm, we create a list of numbers possible and starting from the lowest possible number we discard all multiples on the number in the range and so on. We can start with the smallest prime number, 2, and mark all of its multiples up to “n” as non-primes. Then we repeat the same process for the next available number in the array that is not marked as composite and so on. Finally we can list all the numbers which are not marked prime which would be our result set.

To simplify our logic, whenever we are making an index as nonprime, we can keep a counter of nonprime market numbers and increment it. Initially 1 is marked as non-prime. Since we are only checking till n-1

``num_primes = n - 1 - no_non_primes``

## Complexity Analysis

Time complexity is bounded by loglogN. However the outer loop runs for √n because of the factorisation theorem. Therefore total complexity becomes O(√n * Log(LogN)). We are only storing N + 1 elements for making non-primes, hence space is bounded by O(N).

Time = O(√n * Log(LogN))

Space = O(N)

The proof for the complexity is given here. You can also checkout the discussion on leetcode forum.

## Links for References

Sieve of Eratosthenes | Wiki

Geeks for Geeks

Complexity Proof | Sieve of Eratosthenes

Leetcode Forum Discussion