def test_visual_factorint():
    assert type(factorint(42, visual=True)) == Mul
    assert str(factorint(42, visual=True)) == '2**1*3**1*7**1'
    assert factorint(1, visual=True) is S.One
    assert factorint(42**2, visual=True) == Mul(Pow(2, 2, evaluate=False),
    Pow(3, 2, evaluate=False), Pow(7, 2, evaluate=False), evaluate=False)
    assert Pow(-1, 1, evaluate=False) in factorint(-42, visual=True).args

def test_visual_factorint():
    assert factorint(1, visual=1) == 1
    forty2 = factorint(42, visual=True)
    assert type(forty2) == Mul
    assert str(forty2) == "2**1*3**1*7**1"
    assert factorint(1, visual=True) is S.One
    no = dict(evaluate=False)
    assert factorint(42 ** 2, visual=True) == Mul(Pow(2, 2, **no), Pow(3, 2, **no), Pow(7, 2, **no), **no)
    assert Pow(-1, 1, **no) in factorint(-42, visual=True).args

    def factors(self, limit=None, verbose=False):
        """A wrapper to factorint which return factors of self that are
        smaller than limit (or cheap to compute)."""
        from sympy.ntheory import factorint

        f = factorint(self.p, limit=limit, verbose=verbose).copy()
        for p, e in factorint(self.q, limit=limit, verbose=verbose).items():
            try: f[p] += -e
            except KeyError: f[p] = -e

        if len(f)>1 and 1 in f: del f[1]
        return f

def gf_irred_p_rabin(f, p, K):
    """Rabin's polynomial irreducibility test over finite fields. """
    n = gf_degree(f)

    if n <= 1:
        return True

    _, f = gf_monic(f, p, K)

    x = [K.one, K.zero]

    H = h = gf_pow_mod(x, p, f, p, K)

    indices = set([ n//d for d in factorint(n) ])

    for i in xrange(1, n):
        if i in indices:
            g = gf_sub(h, x, p, K)

            if gf_gcd(f, g, p, K) != [K.one]:
                return False

        h = gf_compose_mod(h, H, f, p, K)

    return h == x

def dup_zz_cyclotomic_poly(n, K):
    """Efficiently generate n-th cyclotomic polnomial. """
    h = [K.one,-K.one]

    for p, k in factorint(n).iteritems():
        h = dup_quo(dup_inflate(h, p, K), h, K)
        h = dup_inflate(h, p**(k-1), K)

    return h

def main():
    i = 1
    while True:
        # nth triangular number is n*(n+1) / 2
        tri = (i*(i+1))/2
        if count_factors(factorint(tri)) >= 1500:
            print tri
            break
        i += 1

def mobius(n):
    dict = factorint(n)
    factor_count = list(dict.values())
    for i in factor_count:
        if i != 1:
            return 0
    if n == 1:
        return 1
    else:
        return (-1) ** (len(factor_count))

def _dup_cyclotomic_decompose(n, K):
    H = [[K.one,-K.one]]

    for p, k in factorint(n).iteritems():
        Q = [ dup_quo(dup_inflate(h, p, K), h, K) for h in H ]
        H.extend(Q)

        for i in xrange(1, k):
            Q = [ dup_inflate(q, p, K) for q in Q ]
            H.extend(Q)

    return H

def solution(q):
    c = 0
    for p in count(start=1, step=1):
        if len(factorint(p)) == q:
            c += 1
            if c == 1:
                last = p
        else:
            c = 0

        if c == q:
            return last

def test_factor():
    assert trial(1) == []
    assert trial(2) == [(2,1)]
    assert trial(3) == [(3,1)]
    assert trial(4) == [(2,2)]
    assert trial(5) == [(5,1)]
    assert trial(128) == [(2,7)]
    assert trial(720) == [(2,4), (3,2), (5,1)]
    assert factorint(123456) == [(2, 6), (3, 1), (643, 1)]
    assert primefactors(123456) == [2, 3, 643]
    assert factorint(-16) == [(-1, 1), (2, 4)]
    assert factorint(2**(2**6) + 1) == [(274177, 1), (67280421310721, 1)]
    assert factorint(5951757) == [(3, 1), (7, 1), (29, 2), (337, 1)]
    assert factorint(64015937) == [(7993, 1), (8009, 1)]
    assert divisors(1) == [1]
    assert divisors(2) == [1, 2]
    assert divisors(3) == [1, 3]
    assert divisors(10) == [1, 2, 5, 10]
    assert divisors(100) == [1, 2, 4, 5, 10, 20, 25, 50, 100]
    assert divisors(101) == [1, 101]
    assert pollard_rho(2**64+1, max_iters=1, seed=1) == 274177
    assert pollard_rho(19) is None

def dup_zz_irreducible_p(f, K):
    """Test irreducibility using Eisenstein's criterion. """
    lc = dup_LC(f, K)
    tc = dup_TC(f, K)

    e_fc = dup_content(f[1:], K)

    if e_fc:
        e_ff = factorint(int(e_fc))

        for p in e_ff.iterkeys():
            if (lc % p) and (tc % p**2):
                return True

def mobius(n):
    primeNos = 0
    if n < 1:
        return "Invalid"
    if n == 1:
        return 1
    for prime, exp in factorint(n).items():
        if exp >= 2:
            return 0
        primeNos = primeNos + 1
    if primeNos % 2 == 0:
        return 1
    else:
        return -1

def isItJamCoin(number):
    binnumber = bin(number)[2:]
    divisors = []
    for i in range(2, 11):
        current = int(binnumber, i)
        if isprime(current):
            return None

        divisor = min(factorint(current).keys())
        if divisor == current:
            return None

        divisors.append(divisor)

    return divisors

def residue_system(n, reduced=False, mod=True):
    """
    @type n: integer > 1
    @type reduced: bool
    @param reduced: return a reduced residue system modulo n or
                    a complete residue system modulo n
    @type mod: bool
    @param mod: use mod when generate final list or not
    @rtype: list

    @return: a residue system modulo n
    """
    assert isinstance(n, int) and n > 1

    if n == 2:
        return [1] if reduced else [0, 1]

    n_fact = factorint(n)

    # if len(n_fact) == 1:
    #     if reduced:
    #         return rrs_of_prime_power(
    #             *list(n_fact.items())[0])
    #     else:
    #         return list(range(n))

    m_list = [pow(*e) for e in n_fact.items()]
    M_list = [n//x for x in m_list]

    if reduced:
        vec = [rrs_of_prime_power(*e)
               for e in n_fact.items()]
    else:
        vec = [list(range(x)) for x in m_list]

    vec = [[x*s for x in l] for l, s in zip(vec, M_list)]

    if mod:
        res = reduce(lambda l1, l2: [(x+y) % n for x in l1 for y in l2],
                     vec)
    else:
        res = reduce(lambda l1, l2: [x+y for x in l1 for y in l2],
                     vec)

    res.sort()

    return res

def test_factorint():
    assert primefactors(123456) == [2, 3, 643]
    assert factorint(0) == {0: 1}
    assert factorint(1) == {}
    assert factorint(-1) == {-1: 1}
    assert factorint(-2) == {-1: 1, 2: 1}
    assert factorint(-16) == {-1: 1, 2: 4}
    assert factorint(2) == {2: 1}
    assert factorint(126) == {2: 1, 3: 2, 7: 1}
    assert factorint(123456) == {2: 6, 3: 1, 643: 1}
    assert factorint(5951757) == {3: 1, 7: 1, 29: 2, 337: 1}
    assert factorint(64015937) == {7993: 1, 8009: 1}
    assert factorint(2**(2**6) + 1) == {274177: 1, 67280421310721: 1}
    assert multiproduct(factorint(fac(200))) == fac(200)
    for b, e in factorint(fac(150)).items():
        assert e == fac_multiplicity(150, b)
    assert factorint(103005006059**7) == {103005006059: 7}
    assert factorint(31337**191) == {31337: 191}
    assert factorint(2**1000 * 3**500 * 257**127 * 383**60) == \
        {2: 1000, 3: 500, 257: 127, 383: 60}
    assert len(factorint(fac(10000))) == 1229
    assert factorint(12932983746293756928584532764589230) == \
        {2: 1, 5: 1, 73: 1, 727719592270351: 1, 63564265087747: 1, 383: 1}
    assert factorint(727719592270351) == {727719592270351: 1}
    assert factorint(2**64 + 1, use_trial=False) == factorint(2**64 + 1)
    for n in range(60000):
        assert multiproduct(factorint(n)) == n
    assert pollard_rho(2**64 + 1, seed=1) == 274177
    assert pollard_rho(19, seed=1) is None
    assert factorint(3, limit=2) == {3: 1}
    assert factorint(12345) == {3: 1, 5: 1, 823: 1}
    assert factorint(
        12345, limit=3) == {4115: 1, 3: 1}  # the 5 is greater than the limit
    assert factorint(1, limit=1) == {}
    assert factorint(0, 3) == {0: 1}
    assert factorint(12, limit=1) == {12: 1}
    assert factorint(30, limit=2) == {2: 1, 15: 1}
    assert factorint(16, limit=2) == {2: 4}
    assert factorint(124, limit=3) == {2: 2, 31: 1}
    assert factorint(4*31**2, limit=3) == {2: 2, 31: 2}
    p1 = nextprime(2**32)
    p2 = nextprime(2**16)
    p3 = nextprime(p2)
    assert factorint(p1*p2*p3) == {p1: 1, p2: 1, p3: 1}
    assert factorint(13*17*19, limit=15) == {13: 1, 17*19: 1}
    assert factorint(1951*15013*15053, limit=2000) == {225990689: 1, 1951: 1}
    assert factorint(primorial(17) + 1, use_pm1=0) == \
        {long(19026377261): 1, 3467: 1, 277: 1, 105229: 1}
    # when prime b is closer than approx sqrt(8*p) to prime p then they are
    # "close" and have a trivial factorization
    a = nextprime(2**2**8)  # 78 digits
    b = nextprime(a + 2**2**4)
    assert 'Fermat' in capture(lambda: factorint(a*b, verbose=1))

    raises(ValueError, lambda: pollard_rho(4))
    raises(ValueError, lambda: pollard_pm1(3))
    raises(ValueError, lambda: pollard_pm1(10, B=2))
    # verbose coverage
    n = nextprime(2**16)*nextprime(2**17)*nextprime(1901)
    assert 'with primes' in capture(lambda: factorint(n, verbose=1))
    capture(lambda: factorint(nextprime(2**16)*1012, verbose=1))

    n = nextprime(2**17)
    capture(lambda: factorint(n**3, verbose=1))  # perfect power termination
    capture(lambda: factorint(2*n, verbose=1))  # factoring complete msg

    # exceed 1st
    n = nextprime(2**17)
    n *= nextprime(n)
    assert '1000' in capture(lambda: factorint(n, limit=1000, verbose=1))
    n *= nextprime(n)
    assert len(factorint(n)) == 3
    assert len(factorint(n, limit=p1)) == 3
    n *= nextprime(2*n)
    # exceed 2nd
    assert '2001' in capture(lambda: factorint(n, limit=2000, verbose=1))
    assert capture(
        lambda: factorint(n, limit=4000, verbose=1)).count('Pollard') == 2
    # non-prime pm1 result
    n = nextprime(8069)
    n *= nextprime(2*n)*nextprime(2*n, 2)
    capture(lambda: factorint(n, verbose=1))  # non-prime pm1 result
    # factor fermat composite
    p1 = nextprime(2**17)
    p2 = nextprime(2*p1)
    assert factorint((p1*p2**2)**3) == {p1: 3, p2: 6}
    # Test for non integer input
    raises(ValueError, lambda: factorint(4.5))

def phi2(n):
    value = n
    for prime, exp in factorint(n).items():
        value = value * (1 - prime ** -1)
    return int(value)

def bestFFTlength(n):
    while max(factorint(n)) >= FACTOR_LIMIT:
        n -= 1
    return n

def count_factors(m):
    prime_fact = factorint(m)
    num = 1
    for k in prime_fact:
        num *= prime_fact[k]+1
    return num

def prime_factors(num):
    primes = factorint(num)
    return sorted(list(ii for k in primes for ii in repeat(k, primes[k])))

@author VegasAce
last modified 11/9/15
'''
import sympy, re, time
from sympy.ntheory import factorint

startTime = time.time()
primeFactors = []
stringFactors = ''
factors = {}
total = 1

 # get the prime factors for each number 1-20
for num in xrange(1,21,1):
     primeFactors.append(factorint(num))

# concatenate those to a string
for num in xrange(0,len(primeFactors),1):
    stringFactors += (str(primeFactors[num]))

# remove all characters but the numbers
stringFactors = re.findall("\d+",stringFactors)

# add the number of factors to a corresponding dictionary
# by key of the factor
for num in xrange(0,len(stringFactors)-1,2):
    if int(stringFactors[num]) in factors.keys():
        if factors.get(int(stringFactors[num])) > int(stringFactors[num+1]):
            continue
        else: