leetcode每日一题：204. 计数质数
题目：
https://leetcode-cn.com/problems/count-primes/
思路：
质数：指在大于 1 的自然数中，只能被 1 和自身整除的自然数。
根据质数的概念，我们首先能够想到的就是直接枚举。
对于每个数 i，我们可以枚举 [2, i-1]区间的任意一个数 j，判断 i能否被 j 整除。这里需要注意的是，这里时间复杂度最差的情况下为 O(n)。但 n 在这里也是一个比较大的数字，单单对一个数字进行判断时，时间复杂度到 O(n)并不理想。
class Solution:
def countPrimes(self, n: int) -> int:
# 质数的属性 只能被1和自己整除
count = 0
# bf
for i in range(2, n):
flag = 0
for j in range(2, i):
if i % j == 0:
flag = 1
break
if flag == 0:
count += 1
return count枚举 [2, i-1] 区间的任意一个数 j，判断 i 能否被 j整除时，我们可以发现，如果 i 能够被 j整除，那么这里的商也一定能够整除 i，即是 i 也能够被i/j 整除。那么我们只要判断 i和i/j其中一个能否整除 i即可。此时我们只要选择判断两者中的较小值，而且我们可以发现较小值一定是落在区间 [2, sqrt(i)]。那么判断每个数i ，枚举时只需要枚举 [2, sqrt(i)]中的数即可。那么此时判断的时间复杂度则可以优化至 O(sqrt(n))
具体的代码实现如下
class Solution:
def countPrimes(self, n: int) -> int:
# 质数的属性 只能被1和自己整除
# 缩短一半
def is_prime(num):
j = 2
while j*j <= num:
if num % j == 0:
return False
j += 1
return True
count = 0
for i in range(2, n):
if is_prime(i):
count += 1
return count埃氏筛
这里说下埃氏筛，这里先放一张关于埃氏筛思路的图片（来源：维基百科）
埃氏筛的原理：从 2 开始，将每个质数的倍数都标记为合数。同样的，标记到 sqrt(n)停止。
假设一个数 i 为质数时，那么此时大于 i且是 i的倍数的数一定不是质数，例如 2i，3i...。那么我们将这些不是质数的数进行标记。
这里需要注意，标记应该从 i * i开始，而不是 2 * i开始。因为对于每个数 i 来说，枚举是从小到大的，此时前面数字的倍数都已经进行了标记。对于 i 而言，2 * i也肯定会被在枚举数字 2 时进行标记，[2, i) 区间的数同理。
class Solution:
def countPrimes(self, n: int) -> int:
# 质数的属性 只能被1和自己整除
is_prime = [1] * n
count = 0
for i in range(2, n):
if is_prime[i]:
count += 1
# 从 i*i 开始标记
for j in range(i*i, n, i):
is_prime[j] = 0
return count本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-12-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
