204.md

204. Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

my thoughts:

1. count all primes from small to n, if a num cannot be divided evenly by any of the primes before it, the num is a prime, add it to the primes list.
This method TLE. a tweak to save some time is instead of checking all the primes before num, only check till p*p > num.

my solution:

**********4715ms
class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 3:
            return 0
        if n == 3:
            return 1
        if n == 4:
            return 2
        res = 2
        i = 5
        primes = [3]
        check = True
        while i<n:            
            for p in primes:
                if i%p == 0:
                    check = False
                    break
                if p*p>i:
                    break
            if check:
                primes.append(i)
            else:
                check = not check
            i += 2
        return len(primes)+1
		
**********revised after using the array mutation method, 1359ms
class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 3:
            return 0
        primes = [True] * n
        primes[0] = primes[1] = False
        for i in range(2, int(n**0.5)+1):
            if primes[i]:
                j = i
                while i*j<n:
                    primes[i*j] = False
                    j += 1
        return sum(primes)

my comments:

iteration is expensive.

from other ppl's solution:

1. when a prime is found, everything that is a multiple of it is not a prime, instead of building a new array every time a prime is found, let's just layout all the possible candidates at once, 232ms:
class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 3:
            return 0
        primes = [True] * n
        primes[0] = primes[1] = False
        for i in xrange(2, int(n ** 0.5) + 1):
            if primes[i]:
                primes[i ** 2::i] = [False] * ((n-i*i-1)/i + 1)
        return sum(primes)