class Solution:
    def countPrimes(self, n: int) -> int:
        n -= 1
        if n < 2:
            return 0
        r = int(n ** 0.5)
        V = [n//d for d in range(1, r + 1)]
        V += list(range(V[-1] - 1, 0, -1))
​
        S = {v: v - 1 for v in V}
        #print(S)
        for p in range(2, r + 1):
            if S[p] == S[p - 1]:
                continue
            p2 = p * p
            sp_1 = S[p - 1]
            for v in V:
                if v < p2:
                    break
                S[v] -= S[v//p] - sp_1
            #print(S)
        return S[n]
​

这个算法是目前最高效的素数算法,只可惜我即使看了解释也不太懂,有人能够对此给出更加“通俗”的解释吗?

 

0 comments
latest

No comments yet.