# natprimeiter
# Not a figure

def prime(n):
  if n == 2 or n == 3: 
    return True
  if n%2 == 0 or n < 2: 
    return False
  for i in range(3, int(n**0.5)+1, 2):
    if n%i == 0:
      return False
  return True


def sieve(n):
  isPrime = [False]*(n+1)
  for i in range(2,n+1):
    isPrime[i] = True

  for p in range(2,n+1):
    if (p*p <= n) and (isPrime[p]):
      for i in range(p*2, n+1, p):
        isPrime[i] = False
        p += 1
  return isPrime