Nerd For Tech
Published in

Nerd For Tech

Swift Leetcode Series: Count Primes

Swift + Sieve of Eratosthenes = 🤔 🧠

You can check out the full explanation on The Swift Nerd blog along with other cool posts on the link above.

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.

Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!

You can find me on TheSwiftNerd | LinkedIn | Github

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store