エラトステネスの篩

qiita.py

n=100
ans=[0]*(n+1)#0は素数候補
ans[0]=ans[1]=1#1は素数でない
i=2
while i*i<=n:
    j=2
    while i*j<=n and ans[i]==0:
        ans[i*j]=1
        j+=1
    i+=1
v=[]
for i in range(n):
    if ans[i]==0:
        v.append(i)
print(v)

#>>>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

最後のところはvに入れなくても良い

test.py

 for i in range(n):
    if ans[i]==0:
        print(i)