(LeetCode)Count Primes — 統計素數(質數)

NO IMAGE

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.

Hint:

  1. Let’s start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than n. The runtime complexity of isPrimefunction
    would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could
    we do better

解題分析:
為了尋求最小的時間複雜度,這裡使用埃拉斯特尼篩選法,
學習連結:
http://blog.csdn.net/u012965373/article/details/52248039
# -*- coding:utf-8 -*-
__author__ = 'jiuzhang'
class Solution(object):
def countPrimes(self, n):
isPrime = [True] * max(n, 2)
isPrime[0], isPrime[1] = False, False
x = 2
while x * x < n:
if isPrime[x]:
p = x * x
while p < n:
isPrime[p] = False
p  = x
x  = 1
return sum(isPrime)