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.

Sieve of Erathosthenes Demo

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

Code

Swift

class Solution {
func countPrimes(_ n: Int) -> Int {
if n < 2 { return 0}
var nonPrimes = [Bool](repeating:false,count: n)
nonPrimes[1] = true
var numNonPrimes = 1
for i in 2..<n {
if nonPrimes[i] == true{
continue
}
var j = 2 * i
while j < n {
if nonPrimes[j] == false {
nonPrimes[j] = true
numNonPrimes += 1
}
j += i
}
}
return n 1 numNonPrimes
}
}
view raw check_prime_.swift hosted with ❤ by GitHub

Python

class Solution:
def countPrimes(self, n):
sieve = [0, 0] + [1] * (n 1)
for k in range(ceil(n**0.5) + 1):
if sieve[k]:
for i in range(k*k, n+1, k):
sieve[i] = 0
return sum(sieve[:1])
view raw check_prime.py hosted with ❤ by GitHub

Java

class Solution {
public int countPrimes(int n) {
if (n < 2) return 0;
boolean[] nonPrime = new boolean[n];
nonPrime[1] = true;
int numNonPrimes = 1;
for (int i=2; i < n; i++) { // O(n)
if (nonPrime[i]) continue;
int j = i * 2;
while (j < n) { // O(log(log(n)))
if (!nonPrime[j]) {
nonPrime[j] = true;
numNonPrimes++;
}
j += i;
}
}
return (n1) numNonPrimes;
}
}
view raw check_prime.java hosted with ❤ by GitHub

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

Leave a Reply

Your email address will not be published. Required fields are marked *