Leetcode204-计数质数

• 题目要求

• 思路

  • 创建一个数组 mylist，长度为 n，数组初始化所有元素为 True
  • 创建另一个数组 res，用来保存质数
  • 数组的 0 下标位置赋值为 Fals，表示 1 不是质数
  • 遍历数组下标 1~n，也就是遍历数字 2 -n，如果当前位置为 True，把当前的元素 append 到结果集里，并把数组 mylist 中，所有当前元素的倍数都置为 False，如果当前位置为 False，xountine 继续下一次循环
  • 最后返回 res 的长度
• 核心代码：

# 初始化标记数组
mylist = [True]*n
# res 用来保存质数
res = []
# 因为 1 不是质数，所以数组下标为 0 的位置置为 False
mylist[0] = False
# 遍历数字 1~n
for i in range(1,n):
    # 如果标记数字是否为质数的值为 False，说明它是某个数的倍数，直接 continue 进入下一次循环
    if mylist[i-1] is False:
        continue
    # 如果为 True
    else:
        # 把当前的数字 append 到结果集中
        res.append(i)
        # 遍历从当前数字开始到结束的数字，步长为当前数组，也就是把当前数字所有的倍数找到，然后把它的数组的标记位置置为 False
        for j in range(i,n,i):
            mylist[j-1] = False
# 返回保存质数结果数组的长度
return len(res)

• 完整代码：

  • 加上了判断给定的 n 值是否小于等于 1

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 1:
            return 0
        mylist = [True]*n
        res = []
        mylist[0] = False
        for i in range(1,n):
            if mylist[i-1] is False:
                continue
            else:
                res.append(i)
                for j in range(i,n,i):
                    mylist[j-1] = False
        return len(res)