Description
Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
描述
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
思路
- 最先想到的方法是一次判断小于n的所有数，对素数进行计数，每次遇到一个素数计数就加一，这种方法可以通过LeetCode测试用例，但是用时较长.
- 此题目使用了埃拉托斯你筛选法.
# -*- coding: utf-8 -*- # @Author: 何睿 # @Create Date: 2019-01-20 21:59:59 # @Last Modified by: 何睿 # @Last Modified time: 2019-01-21 19:19:56 class Solution: def countPrimes(self, n): """ :type n: int :rtype: int """ # 根据题意求小于n的所有素数，小于3（不包括）的数中没有素数 if n < 3: return 0 res, isprime = 0, [True] * (n + 1) # 这道题可以不用把isprime[1]置为False，因为不会从这里统计 isprime[1] = False for i in range(2, int(n**0.5) + 1): if isprime[i]: for j in range(i * i, n + 1, i): isprime[j] = False for i in range(2, n): # 统计素数 if isprime[i]: res += 1 return res
源代码文件在这里.
