目录

一、题目内容

二、解题思路

三、代码

一、题目内容

统计所有小于非负整数 n 的质数的数量。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

提示：

0 <= n <= 5 * 106

二、解题思路

利用厄拉多塞筛法，依次记录质数以及去掉质数的倍数(注意去掉的数可从质数的平方开始)。

三、代码

  

   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def countPrimes(self, n: int) -> int:
     
    
   

    

     

    
    

     
 if n < 3:
     
    
   

    

     

    
    

     
 return 0
     
    
   

    

     

    
    

     

       count = 0
     
    
   

    

     

    
    

     

       is_cut = [False for _ in range(n)]
     
    
   

    

     

    
    

     
 for i in range(2, n):
     
    
   

    

     

    
    

     
 if is_cut[i] is False:
     
    
   

    

     

    
    

     

       count += 1
     
    
   

    

     

    
    

     
 # 所有i的倍数都划去(从i的平方开始)
     
    
   

    

     

    
    

     
 for j in range(i * i, n, i):
     
    
   

    

     

    
    

     

       is_cut[j] = True
     
    
   

    

     

    
    

     
 return count
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       n = 10
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       ans = s.countPrimes(n)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/110519530