# prime.py
# basic prime functions

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


def sievePrimes(n):
  if n < 2:
    return False
  prims = [False]*(n+1)
  for i in range(2,n+1):
    prims[i] = True

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


def primes(n):
  prims = sievePrimes(n)
  return [i for i in range(len(prims)) if prims[i] ]


def countPrimes(a, b):
  # the number of primes a <= x <= b
  x = a
  count = 0
  while x <= b:
    if isPrime(x):
      count += 1
    x += 1
  return count



if __name__ == "__main__":
  print("17 prime?", isPrime(17))
  print("15 prime?", isPrime(15))

  print("\nPrimes: 0 to 100")
  print(sievePrimes(100))
  print(primes(100))

  print("No of primes 2-100:", countPrimes(2, 100))