My (slow) Python solution


  • -1
    D
    def countPrimes(self, n):
            if n < 3:
                return 0
            a=[0,0]+[1]*(n-2)
            c=0
            for i in range(2,n):
                if a[i]==1:
                    k=2
                    while k*i < n:
                        a[k*i]=0
                        k+=1
            return sum(a)

  • -1
    I

    A little change makes it better.

    def countPrimes(self, n):
        if n < 3:
            return 0
        count =[0,0]+[1]*(n-2)
        i = 0
        n = int(math.sqrt(n))+1
        for i in range(2,n):
            if count[i] == 1:
                k = i
                while k*i < n:
                    count[k*i]=0
                    k+=1
        return sum(count)

Log in to reply
 

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