python 线性筛法

解题思路:

注意事项:

参考代码:

n=int(input())
ps=[True]*(n+1)
p=[]
for i in range(2,n+1):
    if ps[i]:
        p.append(i)
    for j in p:
        if i*j>n:
            break
        ps[i*j]=False
        if i%j==0:
            break
for i in p:
    print(i)