Problem statement

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

Solution

This is a very old and classical problem. We are asked to find number of prime numbers in some range, and the most used idea here is to apply so-called sieve of Eratosthenes. The idea is to progressivly remove numbers which are not prime. First, we start with even numbers, that is numbers, which are divisible by 2. Then we remove all numbers, divisible by 3, then by 5 (we skip 4, because it is already divisible by 2) and so on. It is quite easy to code: let us have sieve, where value will be 1 for prime numbers and 0 for not prime. In the beginning we put two first elements as 0, because zero and one are not prime numbers. Then we check if sieve[k] is prime and if it is, we mark numbers k*k, k*(k+1), ... as not primes. It is enough to start with k*k, because any not-prime number have divisor less or equal than its square root.

Complexity

It is O(n*log log n) for time and O(n) for space. For more details please check wikipedia.

Code

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])