组卷题库 > 高中信息技术试卷库
试题详情
筛法求素数。埃拉托斯特尼筛法,简称埃氏筛或爱氏筛,是一种由希腊数学家埃拉托斯特尼所提出的一种简单鉴定素数的算法。要得到自然数 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)

知识点
参考答案
采纳过本试题的试卷
教育网站链接