primes in numbers

primes_in_numbers.py

"""
Given a positive number n > 1 find the prime factor decomposition of n. The result will be a string with the following form :

 "(p1**n1)(p2**n2)...(pk**nk)"
with the p(i) in increasing order and n(i) empty if n(i) is 1.

Example: n = 86240 should return "(2**5)(5)(7**2)(11)"
"""

from collections import defaultdict


def primeFac(orig, n, prime_list, first_primes):
    if n == 1:
        return prime_list
    for prime in first_primes:
        print ("orig={} Trying to divide {} by {} - n % prime = {}".format(orig, n, prime, n % prime)) 
        if n % prime == 0:
            prime_list.append(prime)
            return primeFac(orig, n//prime, prime_list, first_primes_until_n(n//2 +1))
        elif prime > n:
            break
    prime_list.append(n)   
    return prime_list
    
def is_prime(n, first_primes):
    for i in first_primes:
        if n % i == 0:
            return False
    return True
    
def first_primes_until_n(n):
    primes = [2]
    yield 2
    for i in range(3, n, 2):
        if is_prime(i, primes):
            primes.append(i)
            yield i
            # print ("Found prime {}".format(i))
        
def generate_expression(l):
    amounts = defaultdict(int)
    unique = []
    for i in l:
        amounts[i] += 1
        if amounts[i] == 1:
            unique.append(i)
    result = ""        
    for i in unique:
        result += "({}**{})".format(i, amounts[i]) if amounts[i] !=1 else "({})".format(i)
    return result
    
        
    
def primeFactors(n): 
    l = primeFac(n, n, [], first_primes_until_n(n//2 +1))
    exp = generate_expression(l)
    print (exp)
    return exp
    
    
test.assert_equals(primeFactors(7775460), "(2**2)(3**3)(5)(7)(11**2)(17)")
test.assert_equals(primeFactors(7919), "(2**2)(3**3)(5)(7)(11**2)(17)")