素数筛法

步骤

1，把N个自然数按次序排列起来。
2，1不是质数，也不是合数，去掉。
3，第二个数2是质数留下来，而把2后面所有2的倍数都去掉。
4，2后面第一个留下的数是3，把3留下，再把3后面所有3的倍数都去掉。
5，3后面第一个留下的数是5，把5留下，再把5后面所有能被5整除的数都去掉。
6，......将i的倍数去掉......
这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。

代码

n = eval(input("请输入一个数:"))
k = 0
s = [True] * n  # 首先默认所有数都是质数
z = []
for i in range(2,n):
    if s[i]:  # 判断是否为质数，如果没有被标记过，就是质数
        k+=1
        z.append(i)
        for j in range(i+i,n,i):   # 将是指数的倍数的数都改为False
            s[j] = False

print(k) # 个数
print(z) # 质数

例题:Leetcode204. 计数质数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

题解：

class Solution:
    def countPrimes(self, n: int) -> int:
        isPrime = [True] * n
        for i in range(2, int(n ** 0.5) + 1):
            if isPrime[i]:
                for j in range(i * i, n, i):
                    isPrime[j] = False

        count = 0
        for i in range(2, n):
            if isPrime[i]: 
                count += 1

        return count

参考

https://baike.sogou.com/m/fullLemma?lid=70093147
https://developer.aliyun.com/article/1058844
https://labuladong.gitee.io/algo/di-san-zha-24031/shu-xue-yu-659f1/ru-he-gao--e19ec/