Python with explainations


  • 0
    A

    """

    def countPrimes(self, n):
        if n < 2:
            return 0
        isPrime = [True] * n
        isPrime[0] = isPrime[1] = False
        
        for i in range(2, int(math.ceil(math.sqrt(n)))):
            if isPrime[i]:
                for multiples_of_i in range(i * i, n, i):
                    isPrime[multiples_of_i] = False
        
        return sum(isPrime)
    

    """

    Explanations:

    1. Create a list prime flag, assume every num is prime. We will modify flag for all non-prime by finding multiples of each prime.
    2. Multiples of prime p: start from p * p (hence loop p until sqrt(n))

  • 0
    W
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.