Python easy to understand solution.


  • 18
    C
    def countPrimes(self, n):
        if n <= 2:
            return 0
        res = [True] * n
        res[0] = res[1] = False
        for i in xrange(2, n):
            if res[i] == True:
                for j in xrange(2, (n-1)//i+1):
                    res[i*j] = False
        return sum(res)

  • 1
    G

    I think j in second loop should start from i instead of 2

    def countPrimes(self, n):
        if n <= 2:
            return 0
        res = [True] * n
        res[0] = res[1] = False
        for i in xrange(2, n):
            if res[i] == True:
                for j in xrange(i, (n-1)/i+1):
                    res[i*j] = False
        return sum(res)

  • 0
    G

    I used range instead of xrange and got Memory Limit Exceeded. No idea why I had to use xrange for it work properly.


  • 1
    P

    @glang range(1,n) allocates memory to store all the 1...n values. But xrange(1,n) generates them on the fly: in each iteration the next number is generated. So it is better memory wise.


  • 0
    G

    @persianPanda That's interesting! Thanks for letting me know!


Log in to reply
 

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