#!/usr/bin/env python
#using a fast factorial algorithm to ensure that the original script does't 
#break with Python 2.5
#Author: Shriphani Palakodety
#Blog: http://shriphani.com/blog
#Mail: spalakod@cs.purdue.edu

from miller_rabin import *

def multiplicity(n, p):
    """Return the power of the prime number p in the
    factorization of n!"""
    #copied from literateprograms.org
    if p > n: return 0
    if p > n//2: return 1
    q, m = n, 0
    while q >= p:
        q //= p
        m += q
    return m


def makeSeive(n):
	'''Generate a list of primes less than n'''
	a = []
	for i in xrange(3, n, 2):
		if freqCheck(31, twoPower(i-1)[1], twoPower(i-1)[0], i) == "Prime":
			a.append(i)
	return a



def powproduct(ns):
    	"""Compute the explicit value of a factored integer
    	given as a list of (base, exponent) pairs."""
	#copied from literateprograms.org
    	if not ns:
    	    return 1
    	units = 1
    	multi = []
    	for base, exp in ns:
    	    if exp == 0:
    	        continue
    	    elif exp == 1:
    	        units *= base
    	    else:
    	        if exp % 2:
    	            units *= base
   		multi.append((base, exp//2))
    	return units * powproduct(multi)**2


def factorial(n): 
	'''Get the factorial of a number'''
	#copied from literateprograms.org
	return powproduct((p, multiplicity(n, p)) for p in makeSeive(n))	

#tests

print multiplicity(256, 2)
print multiplicity(100, 3)
print multiplicity(50, 29)
print makeSeive(1000)
print factorial(3000)