JuliaでProject Euler(9)

Problem 9

https://projecteuler.net/problem=9

ピタゴラス数は一般に、

 a = l(m^2-n^2), b = 2lmn, c = l(m^2+n^2)と書ける(mnは互いに素でどちらかが偶数で、 n < m < 2n)て、直角三角形の周囲の長さは 2lm(m+n)となるので、周囲の長さ/2を2つの約数に分けて、さらにその一方を2つの約数に分ける必要があるが、mm+nが互いに素なのを利用すると、余分な計算をしなくて済む。

function factorize_naive(n)
    fs = Dict()
    for d in Iterators.countfrom(2)
        if d*d > n
            break
        elseif n%d == 0
            e = 1
            n = div(n, d)
            while n%d == 0
                e += 1
                n = div(n, d)
            end
            fs[d] = e
        end
    end
    if n != 1
        fs[n] = 1
    end
    return fs
end

function f_div(fs1, fs2)
    fs3 = Dict()
    for fac in fs1
        p = fac.first
        e1 = fac.second
        if haskey(fs2, p)
            e = e1 - fs2[p]
            if e != 0
                fs3[p] = e
            end
        else
            fs3[p] = e1
        end
    end
    return fs3
end

function f_value(fs)
    return reduce((x, fac) -> x*fac.first^fac.second, fs, init=1)
end

function divisors(fs)
    L = length(fs)
    if L == 0
        return [Dict()]
    elseif L == 1
        for fac in fs
            p = fac.first
            e = fac.second
            divs = [Dict{Int64,Int64}()]
            append!(divs, [ Dict(p => e1) for e1 in 1:e ])
            return divs
        end
    else
        mid = div(L, 2)
        fss1 = divisors(Dict(Iterators.take(fs, mid)))
        fss2 = divisors(Dict(Iterators.drop(fs, mid)))
        return [ merge(fs1, fs2)
                    for (fs1, fs2) in Iterators.product(fss1, fss2) ]
    end
end

function divisors_coprime(fs)
    w = collect(pairs(fs))
    L = length(w)
    if L == 0
        return [1, 1]
    elseif L == 1
        f = first(fs)
        x = f.first^f.second
        return [1, x]
    else
        v::Array{Int} = []
        mid = div(L, 2)
        for x in divisors_coprime(Dict(w[1:mid]))
            for y in divisors_coprime(Dict(w[mid+1:L]))
                push!(v, x*y)
            end
        end
        return v
    end
end

function divisors3(fs)
    triplets::Array{Tuple{Int,Int,Int}} = []
    num = f_value(fs)
    for fs_ in divisors(fs)
        num1 = f_value(fs_)
        if num1%2 != 0
            continue
        end
        l = div(num, num1)
        for m in divisors_coprime(fs_)
            num2 = div(num1, m)
            n = num2 - m
            if 0 < n && n < m
                push!(triplets, (l, m, n))
            end
        end
    end
    return triplets
end

function Pythagoreans(perimeter)
    fs = factorize_naive(div(perimeter, 2))
    return [ (l*(m*m-n*n), 2*l*m*n, l*(m*m+n*n))
                for (l, m, n) in divisors3(fs) ]
end

function e009(n)
    v = Pythagoreans(n)
    println(length(v), v)
    return reduce(*, v[1])
end

N = parse(Int, ARGS[1])
println(e009(N))

素因数分解は、Dict(p=>e)で表している。
ここで、mergeはDict同士をmergeしている。

julia> dic1 = Dict(1=>2, 2=>3)
Dict{Int64,Int64} with 2 entries:
  2 => 3
  1 => 2

julia> dic2 = Dict(3=>3, 4=>2)
Dict{Int64,Int64} with 2 entries:
  4 => 2
  3 => 3

julia> merge(dic1, dic2)
Dict{Int64,Int64} with 4 entries:
  4 => 2
  2 => 3
  3 => 3
  1 => 2

ここではこれがたまたまハマっているが、そんなに使わないと思われる。
Iterators.takeとIterators.drop素因数分解を半分に使っている。それぞれ、第2引数の個数まで取る、あるいは落としている。