factorize.jl

# factorization algorithm based on gcd
#
# could be vastly improved, this is barely better than
# naive

function fac(n::BigInt)
    factors = Dict{BigInt,BigInt}()

    while !isprime(n::BigInt)
        # this could be waay more efficient
        for i = 2:ceil(sqrt(n))::BigInt
            d = gcd(i,n)::BigInt

            if d == 1
                continue
            elseif isprime(d)
                if getkey(factors,d,0) == 0
                    factors[d] = 0
                end

                factors[d] += 1

                n = div(n,d)::BigInt
                break
            else
                # Deal with this in a recursive way
                println("Composite factor")
            end
        end
    end

    # get the last factor
    d = n
    if getkey(factors,d,0) == 0
        factors[d] = 0
    end

    factors[d] += 1

    return factors
end

n = BigInt(10)
n ^= 25;
n += BigInt("223452345639875623948");

println(fac(n))