Count Primes

Problem: Count Primes

The traditional way to count primes is to iterate through all the primes and judge whether it's an prime. However, judging a number is a prime or not takes us too much time. So we'd better skip those numbers which can't be primes.

For example, when we are dealing with number 2, we can known that 4, 6, 8, ... are not primes. Besides, when we are dealing with number 5, we can start marking non-primes from 25 because all numbers smaller than 25 which can be divided by 5 should already been counted before.

Code in Python:

from math import sqrt

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        isPrime = [True] * n
        for i in xrange(2, int(sqrt(n))+1):
            if not isPrime[i]:
                continue
            for j in xrange(i * i, n, i):
                isPrime[j] = False
        count = 0
        for isPrime in isPrime[2:]:
            if isPrime:
                count += 1
        return count