接外包,有相关需求的可以联系我:Telegram | Email

Count Primes

该文章创建(更新)于03/31/2022,请注意文章的时效性!

Given an integer n, return the number of prime numbers that are strictly less than n.

Solution

Code

  • python
class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 1:
            return 0

        tmp = [True] * n

        for i in range(2, n):
            if(tmp[i]):
                for j in range(i*i, n, i):
                    tmp[j] = False

        ret = 0
        for i in range(2, n):
            if tmp[i]:
                ret += 1

        return ret
  • full code
import math
class Solution:
    def countPrimes(self, n):
        if n <= 1:
            return 0

        tmp = [True] * n

        # i的倍数都是合数
        # 逆向思维
        for i in range(2, n):
            # 可以有效避免重复计算
            if(tmp[i]):
                for j in range(i*i, n, i):
                    tmp[j] = False
        #从头开始计算
        ret = 0
        for i in range(2, n):
            if tmp[i]:
                ret += 1

        return ret

    # def isPrime(self,x):
    #     for i in range(2, int(math.sqrt(x))+1):
    #         if (x % i == 0):
    #             return False
    #     return True

S = Solution()
# print("********************************")
# print(S.countPrimes(10))
print(S.countPrimes(1500000))


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2022/03/31/count-primes/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码