Difficulty: Easy Link: Day 2: May LeetCode Challenge
Count the number of prime numbers less than a non-negative number,
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
0 <= n <= 5 * 106
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
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)