0204._count_primes.md

Navigation

• Navigation
• Links:
• Solution 1 暴力，超时
• Solution 2 优化暴力，超时
• Solution 3 埃氏筛法

Links:

1. https://leetcode.com/problems/count-primes/
2. https://leetcode-cn.com/problems/count-primes/

Solution 1 暴力，超时

class Solution:
    def countPrimes(self, n):
        res = 0

        for i in range(2, n):
            for j in range(2, i):
                if i % j == 0:
                    break
            else:
                res += 1
        
        return res

Solution 2 优化暴力，超时

class Solution:
    def countPrimes(self, n):
        res = 0
        
        for i in range(2, n):
            for j in range(2, int(i ** 0.5) + 1):
                if i % j == 0:
                    break
            else:
                res += 1
                
        return res

Solution 3 埃氏筛法

1. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
2. 比如求20以内质数的个数,首先0，1不是质数。2是第一个质数，然后把20以内所有2的倍数的flag设置为0。2后面紧跟的数即为下一个质数3，然后把3所有的倍数的flag设置为0。3后面紧跟的数即为下一个质数5，再把5所有的倍数的flag设置为0。以此类推。

class Solution:
    def countPrimes(self, n):
        if n < 2:
            return 0
        
        primes = [1] * n
        primes[0] = primes[1] = 0

        for i in range(2, int(n ** 0.5) + 1):
            if primes[i]:
                primes[i * i: n: i] = [0] * len(primes[i * i: n: i])
        
        return sum(primes)