浙江省钱塘联盟2023-2024学年高二上学期信息技术期中联考试卷试题详情

筛法求素数。埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单鉴定素数的算法。要得到自然数 n 以内的全部素数，必须把不大于根号 n 的所有素数的倍数剔除，剩下的就是素数。

算法思想：先用 2 去筛，即把 2 留下，把 2 的倍数剔除掉；再用下一个质数，也就是 3 筛，把3 留下，把 3 的倍数剔除掉；接下去用下一个质数 5 筛，把 5 留下，把 5 的倍数剔除掉；不断重复下去……

现在使用埃氏筛法求 1～n 之间的素数个数，代码如下：

n=int(input())

a=[1]*(n+1)

a[0],a[1]=0,0 #标记小于 2 的数, 0 表示非素数，1 表示素数

    ①   i=2

while i<=n:

    if   ②   :

        for j in range(2*i,n+1,i):

            a[j]=0

    i+=1

for i in range(n+1):

      ③   print(num)

扫码查看试题答案 登录查看答案