204. 数素数

Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10Output: 4Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

It is to find how many prime numbers are smaller than n

Here we use the method of prime number sieve to reduce the time complexity to linear time. The basic idea of ​​prime number sieve is that a multiple of a prime number must not be a prime number

https://en.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95#Python_3.6

Easy to understand version:

class Solution:def countPrimes(self, n: int) -> int:ispri=[0,0]+[1]*(n-2)if n==0 or n==1:return 0for i in range(2,int(n**0.5)+1):if ispri[i]:for j in range(i*i,n,i):ispri[j]=0return sum(ispri)

Use the list operator skillfully, the result slightly improves the operation time

 def countPrimes(self, n: int) -> int:ispri=[0,0]+[1]*(n-2)if n==0 or n==1:return 0for i in range(2,int(n**0.5)+1):if ispri[i]:ispri[i**2::i]=[0]*(len(ispri[i**2::i]))return sum(ispri)