Finding Primes and Factorization

primes.py

from itertools import takewhile

def sieve(n):
  """Sieve of Eratosthenes
  
  Returns a list of primes from 2 to n.
  """
  
  if n < 2:
    return []
  
  nums = list(range(n+1))
  
  nums[0] = nums[1] = None
  
  i = 2
  
  while i*i <= n:
    
    for p in range(i*i, n+1, i):
      nums[p] = None
    
    i += 1
    
    while i*i <=n and nums[i] is None:
      i += 1
  
  return list(filter(None, nums))
  

def factorize(n):
  """Finds and yields tuples of (prime, x) for n 
  where prime is a prime factor and x is the number of
  time it appears as a factor.
  
  list(factorize(6*7*8)) -> [(2,4), (3,1), (7,1)]
  """
  
  if n in (-1, 0, 1):
    yield (n, 1)
  
  else:
    if n < 0:
      yield (-1, 1)
      n = -n
    
    primes = sieve(n)
    
    if n in primes:
      yield (n, 1)
    
    else:
      # no factors greater than half of n
      for prime in takewhile(lambda p, n=n: p <= n//2, primes):
        i = 0
        
        while not n % prime:
          i += 1
          n //= prime
        
        if i:
          yield (prime, i)