動機

之前是用ruby的buildin作弊阿wwwww

Problem

Count the number of prime numbers less than a non-negative number, n.

 

Example 1:

Input: n = 10Output: 4Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:

Input: n = 0Output: 0

Example 3:

Input: n = 1Output: 0

 

Constraints:

  • 0 <= n <= 5 * 106

Sol

這不是最快的，但是是最好玩的

gen_primes(source)中的D是放key的某些因數，因為key本身是質數的倍數，所以可以自己加一個質數來往前找倍數

class Solution:
    def countPrimes(self, n: int) -> int:
        def primes():
            def odds():
                n = 3
                while True:
                    yield n
                    n += 2
            yield 2
            ps = [2]
            for n in odds():
                isPrime = True
                for p in ps:
                    if n % p == 0:
                        isPrime = False
                if isPrime:
                    yield n
                    ps.append(n)
        def gen_primes():
            def ints():
                n = 2
                while True:
                    yield n
                    n += 1
            D = {}
            for q in ints():
                if q not in D:
                    yield q
                    D[q * q] = [q]
                else:
                    for p in D[q]:
                        D.setdefault(p + q, []).append(p)
                    del D[q]
        
        ret = 0
        for x in gen_primes():
            if n > x:
                ret+=1
            else:
                break
        return ret