Count Primes

题目描述

解题方法

最简单的做法

对小于n的每一个数，检查它是否能被小于它的数整除，O(n^2)

倍数去除法

• 先建立一个都是True的长度为n的array, 代表Index为i的是否是prime
• 从2开始到N-1,可以分别不断地将它们的倍数设为False

优化1

这里就有技巧了，去掉2的所有倍数，再去掉3的所有倍数，当去掉4的倍数时，因为4已经被2去掉，所以4的倍数也肯定是2的倍数。 所以我们在去掉k的倍数时，先check k是否还为prime, 如果已经不是，说明k已经被小于他的因数去掉，就可以跳过了

优化2

Let's write down all of 12's factors:

2 × 6 = 12
3 × 4 = 12
4 × 3 = 12
6 × 2 = 12

As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n. Yes, the terminating loop condition can be p < √n, as all non-primes ≥ √n must have already been marked off.

sieve of eratosthenes

The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to n. But don't let that name scare you, I promise that the concept is surprisingly simple. http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity

Solution

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

        result = 0
        for bl in isPrime:
            if bl:
                result += 1
        return result

Reference