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的位置置为Falsemylist[0] = False# 遍历数字1~nfor 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)