204. Count Primes

Given an integer n, return the number of prime numbers that are strictly less than n.

Note: We only need to use the primes until sqrt(n), because the remaining

primes are already marked by initialization. We are only detecting

non-primes.

      The start range is p*p. p+p would also work but less efficient.

      

def countPrimes(n: int):

    if n <= 2:

        return 0

    numbers = [False, False] + [True] * (n - 2)

    for p in range(2, int(sqrt(n)) + 1):

        if numbers[p]:

            # Set all multiples of p to false because they are not prime.

            for multiple in range(p * p, n, p):

                numbers[multiple] = False

    return sum(numbers)

   

   

def countPrimesMyAlgo(self, n: int):    

    if n <= 2:

        return 0    

    primes = [2]

   

    def isPrime(x):

        for p in primes:

            if x % p == 0:

                return False

            if p * p >= x:

                break

        primes.append(x)

        return True