寻找质数—埃式筛法
寻找质数—埃式筛法
生信编程日常
发布于 2020-08-25 09:55:40
发布于 2020-08-25 09:55:40
leetcode上的204题，寻找小于非负数n的质数个数。
这个题，用暴力法肯定会超时，优化一点的暴力法还是会超时。一般来说，寻找质数主要是两种方法，埃式筛和欧拉筛。
埃式筛即埃拉托斯特尼筛法，也叫厄拉多塞筛法。这是由古希腊数学家埃拉托斯特提出来的，该算法是说要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
python实现：
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0
res = [1 for i in range(n)]
res[0], res[1] = 0, 0
p = 2
while p < int(n ** 0.5) + 1:
if res[p]: # 如果是质数，将所有质数的倍数都改为0
for i in range(p ** 2, n, p): 在p**2之前的已经计算过了
res[i] = 0
p += 1
return sum(res)本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读