エラトステネスのふるい

エラトステネスのふるい

・任意のn以下の素数のリストをO(nloglogn)（らしい）で得る。

def prime(x):
  x = int(x)
  if x < 2:
    return []
  P = [True]*(x+1)
  P[0],P[1] = False,False
  res = []
  for i in range(x+1):
    if P[i] == False:
      continue
    else:
      res.append(i)
      q = i*2
      while q < x+1:
        P[q] = False
        q += i
  return res

入力

#input
p = prime(100)
print(p)

出力

#output
[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]