204. 计数质数

https://leetcode-cn.com/problems/count-primes/

解法一：暴力（超时）

遍历从2到n的所有数，每次用一个质数检测函数检验。检测原理是看n能否整除2到n，只要有一个，n就不是质数，实际上只用检测2到√n即可，因为n以内的素数不会超过√n。

class Solution:
    def countPrimes(self, n: int) -> int:
        count = 0
        for i in range(2, n):
            if self.isPrime(i):
                count += 1
        return count
    
    #检验是否为质数
    def isPrime(self, n):
        i = 2
        #实际上检测能否整除[2, √n]范围即可
        #用乘法代替开平方函数，提高速度
        while i ** 2 <= n:
            if n % i == 0:
                return False
            i += 1
        return True

解法二：埃拉托斯特尼筛法

伪代码，摘自维基百科：

Input: an integer n > 1
 
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
 
 for i = 2, 3, 4, ..., not exceeding sqrt(n):
   if A[i] is true:
     for j = i², i²+i, i²+2i, i²+3i, ..., not exceeding n :
       A[j] := false
 
Output: all i such that A[i] is true.

class Solution:
    def countPrimes(self, n: int) -> int:
        isPrime = [True] * (n)  #标志数组
        #筛法
        i = 2
        while i ** 2 < n:
            if isPrime[i] == True:
                for j in range(i**2, n, i):  #i², i²+i, i²+2i, i²+3i...
                    isPrime[j] = False
            i += 1
        #统计素数    
        count = 0
        for i in range(2, n):
            if isPrime[i] == True:
                count += 1
        return count

其实用sqrt速度也差不多，还简洁：

class Solution:
    def countPrimes(self, n: int) -> int:
        isPrime = [True] * (n)  #标志数组
        #筛法
        for i in range(2, int(math.sqrt(n))+1):
            if isPrime[i] == True:
                for j in range(i**2, n, i):
                    isPrime[j] = False
        #统计素数    
        count = 0
        for i in range(2, n):
            if isPrime[i] == True:
                count += 1
        #print(isPrime)
        return count