wordpress设置联系表格,咸阳seo推广,网站首页英文,益阳一站式网站建设公司题目#xff1a; 给定整数 n #xff0c;返回 所有小于非负整数 n 的质数的数量 。 来源#xff1a;力扣#xff08;LeetCode#xff09; 链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 示例#xff1a; 示例 1#xff1a; 输… 题目 给定整数 n 返回 所有小于非负整数 n 的质数的数量 。 来源力扣LeetCode 链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 示例 示例 1 输入n 10 输出4 解释小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。 示例 2 输入n 0 输出0 示例 3 输入n 1 输出0 解法 采用Sieve of Eratosthenes核心思想是数2,3,4……n依次去除2的倍数3的倍数4的倍数…… 举例假设2,3,4……100先把2的倍数全部去掉从2的平方开始去剩下2,3,5,7,9……99。接着把3的倍数全部去掉从3的平方开始去剩下2,3,5,7……97。从平方开始去的原因是一个合数可能由多组因数组成要么两个因数相同要么一大一小对于一大一小的情况理想的处理方式是遇到小因数的时候去掉合数遇到大因数的时候不再考虑。而从平方开始去有助于实现这一思路。比如6遍历2的时候已经去掉了所以遍历3的时候没必要考虑直接从9开始去。因为最小的因数是2并且2的2倍和平方相等所以不会有遗漏所以没必要考虑3*2,4*3等类似情况直接从3*3,4*4开始去。 因为每次从平方开始去所以只需要遍历到n的开方就可以了。 代码 class Solution:def countPrimes(self, n: int) - int:if n 3:return 0nums [0, 0] [1] * (n - 2)for index in range(2, int(n ** 0.5) 1):if nums[index]:nums[index * index::index] [0] * len(nums[index * index::index])return sum(nums)
