力扣204题(如何高效寻找素数)

204题、计数质数

基本思想:

筛数法

具体实现:

1、从2向后遍历,每遇到一个数字,将其倍数所对应的 is_prime 设为False,
因此遇到新的数字num,is_prime[num]=True说明它不是任何2..num-1的数字的倍数,即质数。

代码:

def countPrimes(n):
    is_prime = [True]*(n+1)
    ans = 0
    for num in range(2,n+1):
        if is_prime[num]:
            ans+=1
            for k in range(1,n//num+1):
                is_prime[num*k]=False
    return ans

 

上一篇:Codeforces Round #725 (Div. 3)


下一篇:P5736 质数筛