def least_common_multiple(divisors=range(1, 21)):
    # Returns least common multiple of INTs in <divisors>

    # No matter the divisors, we at least need the max divisor as an LCM
    lcm = max(divisors)
    lcm_factors = sympy.factorint(lcm)

    for n in divisors:
        n_factors = sympy.factorint(n)

        for f in n_factors:

            # If this factor appears in the LCM ...
            if f in lcm_factors:
                factor_excess = lcm_factors[f] - n_factors[f]

                # ... check if there are enough of them
                if factor_excess < 0:

                    # If not, we multiply into LCM to account for this
                    lcm *= - factor_excess * f
                    lcm_factors[f] += - factor_excess

            # If this factor does not appear in the LCM, multiple into LCM
            else:
                lcm *= n_factors[f] * f
                lcm_factors[f] = n_factors[f]

    return lcm

def main():
        print "euler23.py"
        print sum(proper_factors(28))
        print deficient(28)
        print perfect(28)
        print factorint(28)
        abridged_abundant = lambda(x): x%6 != 0 and x%28 != 0 and x%496 != 0 and abundant(x)
        print ascuii_map([('X', abridged_abundant), (' ', nil)], ['list', 0, 8000, 60])

def main():
    count = 0
    min = 2 * 3 * 5 * 7
    while True:
        if len(sympy.factorint(min)) == 4:
            count = count + 1
        else:
            count = 0
        if count == 4:
            print ("%d" % (min - 3))
            print(sympy.factorint(min - 3))
            break
        min = min + 1

def euler47():
    i = 646
    while True:
        i += 1
        if all(len(factorint(i+j).keys()) == 4 for j in range(4)):
            print(i)
            return

def is_semiprime(n):
    factors = sym.factorint(n)
    if len(factors) == 2:
        return n
    if len(factors.values()) == 1 and list(factors.values())[0] == 2:
        return n
    return 0

def primes_pop(a):
    if isinstance(a, int):
        if a < 2:
            return []
        try:
            import sympy
            factor_dict = sympy.factorint(a)
            factors_with_mult = [[fact for _ in range(factor_dict[fact])] for fact in factor_dict]
            return sorted(sum(factors_with_mult, []))
        except:
            working = a
            output = []
            num = 2
            while num * num <= working:
                while working % num == 0:
                    output.append(num)
                    working //= num
                num += 1
            if working != 1:
                output.append(working)
            return output
    if is_num(a):
        return cmath.phase(a)
    if is_seq(a):
        return a[:-1]
    raise BadTypeCombinationError("P", a)

def factor(expression, variable = None, ensemble = None, decomposer_entiers = True):
    if isinstance(expression, (int, long, Integer)):
        if decomposer_entiers:
            return ProduitEntiers(*factorint(expression).iteritems())
        else:
            return expression


    elif isinstance(expression, Basic) and expression.is_polynomial():
        if variable is None:
            variable = extract_var(expression)
        if variable is None:
            # polynôme à plusieurs variables
            return factor_(expression)
        else:
            try:
                return poly_factor(expression, variable, ensemble)
            except NotImplementedError:
                if param.debug:
                    print_error()
                return expression
    resultat = together_(expression)
    if resultat.is_rational_function():
        num, den = resultat.as_numer_denom()
        if den != 1:
            return factor(num, variable, ensemble, decomposer_entiers)/factor(den, variable, ensemble, decomposer_entiers)
    else:
        resultat = auto_collect(resultat)
        if resultat.is_Mul:
            produit = 1
            for facteur in resultat.args:
                if facteur != 1:
                    produit *= factor(facteur, variable, ensemble, decomposer_entiers)
            return produit
        return resultat

	def operate(self, a):
		if isinstance(a, int):
			if a < 0:
				# Primality testing
				return len(self.operate(-a)) == 1
			if a < 2:
				return []
			try:
				from sympy import factorint
				factor_dict = factorint(a)
				factors_with_mult = [[fact for _ in range(
					factor_dict[fact])] for fact in factor_dict]
				return sorted(sum(factors_with_mult, []))
			except:
				working = a
				output = []
				num = 2
				while num * num <= working:
					while working % num == 0:
						output.append(num)
						working //= num
					num += 1
				if working != 1:
					output.append(working)
				return output
		if is_num(a):
			return cmath.phase(a)
		if is_seq(a):
			return a[:-1]
		raise BadTypeCombinationError("P", a)

 def apply(self, n, evaluation):
     'FactorInteger[n_]'
     
     if isinstance(n, Integer):
         factors = sympy.factorint(n.value)
         factors = sorted(factors.iteritems())
         return Expression('List', *[Expression('List', factor, exp) for factor, exp in factors])
     elif isinstance(n, Rational):
         factors = sympy.factorint(n.value.numer())
         factors_denom = sympy.factorint(n.value.denom())
         for factor, exp in factors_denom.iteritems():
             factors[factor] = factors.get(factor, 0) - exp
         factors = sorted(factors.iteritems())
         return Expression('List', *[Expression('List', factor, exp) for factor, exp in factors])
     else:
         return evaluation.message('FactorInteger', 'exact', n)

 def factor(self, n):
     """Simple example of specific protocol functionality
     """
     log.msg('Factor ', n)
     f = factorint(long(n))
     log.msg('Factors: ', str(f))
     return 

def decodersa(n, e, c):
    
    # using sympy factor int function obtain p,q.
    # takes significant time for long numbers
    primes = factorint(n)
    
    p, _ = dict.popitem(primes)
    q, _ = dict.popitem(primes)

    p1, q1 = p-1, q-1

    # check p-1 and q-1
    if not(gcd(p1 * q1, n) == 1):
        raise Exception('Incorrect p-1 and q-1, their GCD is not 1')
  
    p1q1 = p1 * q1

    # now we solve e*d = 1 (mod (p-1)(q-1))
    # e^-1 (mod (p-1)(q-1))
    e1 = modinv(e, p1q1)

    # check that e1 is e's modular inverse
    if not(pow(e * e1, 1, p1q1) == 1):
        raise Exception('Incorrect e^-1 and e, e*e^-1 not 1')

    # solve for d
    d = e1 % p1q1

    # solve c^d (mod n)
    decoded = pow(long(c), d, n)

    return num2alph(str(decoded))

def factor_special(n):
    dic1 = sympy.factorint(n)
    dic2 = {}
    for i in dic1:
        if dic1[i] != 1:
            dic2[i] = dic1[i]//2
    return dic2

def fac_list(n):
    f_list = [1]
    prime_fac_dict = sympy.factorint(n)
    for i, j in prime_fac_dict.items():
        f_list.extend([a * i ** k for a in f_list[:] for k in range(1, j+1)])
    f_list.remove(n)
    return f_list

def phi(n):
    factor = list(factorint(n))
    
    phi = n
    for i in range(1, len(factor) +1):
        for j in combinations(factor, i):
            phi += (-1) ** i * (n // product(j))
    return phi

def omega(nval):
    if nval == 1:
        return 0
    if nval in prime_exponent_dicts:
        pd = prime_exponent_dicts[nval]
    else:
        pd = sympy.factorint(nval)
        prime_exponent_dicts[nval] = pd
    return len(pd)

def phi(n):
    if isPrime(n):
        return n-1
    else:
        factors = factorint(n)
        res = n
        for f in list(factors.keys()):
            res = res*(1 - 1/f)
    return res

 def eval(cls, expr):
     if expr.is_Integer:
         from sympy import factorint
         factors = factorint(Abs(expr), limit=10000)
         factorlist=list(factors.keys())
         factorlist.sort()
         return factorlist[0]
     else:
         raise ValueError("Argument to smallest_factor must be an integer")

def main():
    ''' main function '''
    while True:    # input value <= zero to exit
        val = input("input an postive integer (0 to quit): ")
        val = int(val)
        if val <= 0:
            break
        fdict = factorint(val)
        print(fdict)

def radical(n):
    """A radical is the product of distinct prime factors

    For example, 504 = 2^3 x 3^2 x 7, so radical(504) = 2 x 3 x 7 = 42

    >>> radical(504)
    42
    """
    return product(sympy.factorint(n).keys())

def fun(n):
    if n == 1:
        return 1
    factor_list = [1]
    for i, j in sp.factorint(n).items():
        for s in factor_list[:]:
            for t in range(1, j + 1):
                factor_list.append(s * i ** t)
    factor_list.remove(n)
    return sum(factor_list)