|| from Hubert Jin
|| prime number factorization

factors n = [k | k <- [2..n]; n mod k = 0]

isprime p = (factors p = [p])

findprimes = filter isprime [2..]

all_factors n = [[1,n]], (isprime n)
              = check 0 n, otherwise
                where check i n = [], i>n
                                = [[1,pri]] ++ (check i (n div pri)), isfactor
                                = check (i+1) n, otherwise
                                  where isfactor = (n=(n div pri)*pri)  
                                        pri = findprimes ! i

list_form n = reverse (standard (all_factors n))
list_f [] = []
list_f (a:s) = (make a) ++ " * " ++ (list_f s), s~=[]
             = (make a), otherwise
               where make a = (shownum (a!1)) ++ "^" ++ (shownum (a!0)),(a!0)~=1
                            = (shownum (a!1)),(a!0)=1

standard s = s, #s<2
           = my_merge (standard s1) (standard s2), #s>1
             where s1 = take (#s div 2) s
                   s2 = drop (#s div 2) s

my_merge [] y = y
my_merge x [] = x
my_merge (a:s1) (b:s2) = [[((a!0)+(b!0)),a!1]] ++ (my_merge s1 s2), ((a!1)=(b!1) & ~cancel)
                       = [a] ++ (my_merge s1 (b:s2)), ((a!1)>(b!1) & ((a!0)~=0))
                       = [b] ++ (my_merge (a:s1) s2), ((a!1)<(b!1) & ((b!0)~=0))
                       = my_merge s1 s2, otherwise
                         where cancel = (((a!0)+(b!0)) = 0)

interesting a = (shownum a) ++ " == " ++ (list_f (list_form a)) ++ "\n"

fun i = (interesting i) ++ (fun (i+1))