给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0
输出：0
示例 3：
输入：n = 1
输出：0
提示：
0 <= n <= 5 * 106
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/count-primes/
- 方法1： 暴力查找，时间超时
class Solution:
def countPrimes(self, n: int) -> int:
def isPrime(x):
for i in range(2, int(x**0.5)+1):
if x%i==0:
return False
return True
cnt = 0
for i in range(2, n):
if isPrime(i):
cnt = cnt+1
return cnt
- 方法二：埃氏筛
class Solution:
def countPrimes(self, n: int) -> int:
is_prime = [1 for i in range(0,n)]
for i in range(2, n):
if is_prime[i]:
for j in range(i*i, n, i):
is_prime[j] = 0
count = sum(is_prime[2:])
return count
- 方法三： 线性筛
class Solution:
def countPrimes(self, n: int) -> int:
prime = []
is_prime = [1 for i in range(0, n)]
for i in range(2, n):
if is_prime[i]:
prime.append(i)
for j in prime:
if i*j>=n: break
is_prime[i*j] = 0
if i%j==0: break
return len(prime)