find_missing_with_primes.py

from operator import mul

#find what numbers we are missing from an unordered list of size 1 to k, where numbers are bounded by n-k
def missing_n_prime(upto,missing_some):
  product_1_to_n_primes = reduce(mul,[nth_prime(n) for n in xrange(upto)])
  product_missing = reduce(mul, [nth_prime(n-1) for n in missing_some])
  prime_factors = prime_factorize(product_1_to_n_primes/product_missing)
  return [what_number_prime(i) for i in prime_factors]

#get prime factors of a number
def prime_factorize(n):
  factors = []
  if n==None:
    return factors
  i = 0
  not_done = True
  while not_done:
    if n==0:
      not_done = False
    elif is_prime(n):
      factors.append(n)
      not_done = False
    else:
      prime = nth_prime(i)
      if n % prime == 0:
        n /= prime
        factors.append(prime)
        i = 0
      else:
        i += 1
  return factors

#given a prime number, find out the n for which nth_prime would be equal to it
def what_number_prime(i):
  if i == 2:
    return 1
  elif i%2 == 0:
    return -1
  else:
    num = 1
    while i > 2:
      if is_prime(i):
        num += 1
      i -= 2
    return num