204. Count Primes

王笑朝发布于2019-07-30 16:58 / 2727人阅读

摘要：题目链接思路首先要知道如何判断一个数字是否为素数。具体方法可以看这里其次，如果朴素的判断，那么会因为效率底下而超时。所以在我们每次找到素数的时候，可以把素数的倍数都标记为非素数。这样可以节省轮询的时间。算法复杂度时间空间代码

题目链接：Counting Primes

思路：
首先要知道如何判断一个数字是否为素数。具体方法可以看这里

其次，如果朴素的判断，那么会因为效率底下而超时。
所以在我们每次找到素数的时候，可以把素数的倍数都标记为非素数。这样可以节省轮询的时间。

算法复杂度：

时间：O(nloglogn) (time complexity for Sieve of Eratosthenes Algorithm)
空间：O(n)

代码：

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 3:
            return 0
        primes = [True] * n
        primes[0] = primes[1] = False
        for i in range(2, int(n**0.5)+1):
            if primes[i]:
                for j in range(i*i, n, i):
                    primes[j] = False
        
        return sum(primes)

云服务器 GPU云服务器 Primes Model 204 Count hbase count 命令

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/41937.html

[LeetCode] 204. Count Primes

Problem 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. Solution class Solut...

cheukyin 2019-08-16 13:38 评论0 收藏0
[Leetcode] Count Primes 数素数

摘要：利用这个性质，我们可以建立一个素数数组，从开始将素数的倍数都标注为不是素数。第一轮将等表为非素数，然后遍历到，发现没有被标记为非素数，则将等标记为非素数，一直到为止，再数一遍素数数组中有多少素数。代码将的倍倍倍都标记为非素数 Count Primes Description: Count the number of prime numbers less than a non-nega...

Achilles 2019-08-14 12:28 评论0 收藏0
leetcode部分题目答案之JavaScript版

摘要：自己没事刷的一些的题目，若有更好的解法，希望能够一起探讨项目地址自己没事刷的一些LeetCode的题目，若有更好的解法，希望能够一起探讨 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 评论0 收藏0
[LeetCode] Count Primes

摘要：用数组标记非质数，每当出现一个为，计数器加一。关于质数有三点大于的质数一定是奇数，如，，奇数中的非质数也一定是奇数的乘积。首先，我们用从到进行标记。标记完所有的合数之后，再用到之间的遍历，所有未被标记的质数。 Problem Count the number of prime numbers less than a non-negative number, n. Note 用数组fla...

Shisui 2019-08-14 15:54 评论0 收藏0
线性素数筛选（linear sieve for prime number）

摘要：转载到其他平台前也请通知我。算法分析由于我们每次寻找的素数时，都从开始，逐渐上除，最后到为止，确认是否是素数。接着继续排除其有关合数。在速度上有略微提升，但是它的算法是主动忽略的相关合数，实际意义并不是很大。偶然发现了这个和stackoverflow很像的地方。打算写些专栏，一方面，记录自己学到的东西。另一方面，也把这些分享给大家。无论是内容错误还是解释方式不好，都欢迎各位拍砖。转载...

biaoxiaoduan 2019-07-24 18:07 评论0 收藏0