My python solution


  • 1
    P
    class Solution:
        # @param {integer} n
        # @return {integer}
        def countPrimes(self, n):
            if n <= 2:
                return 0
            else:
                primes = [0,0] + [1]*(n-2)
                nsqrt = int((n-1)**(0.5))
                for i in range(2,nsqrt+1):
                    if primes[i] == 1:
                        for j in range(i**2,n,i):
                            primes[j] = 0
                return sum(primes)

Log in to reply
 

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