MojoでProject Euler 75

https://projecteuler.net/problem=75

直角三角形の辺は、

と表されるので、周囲の長さLは、

となります。なので、を当てはめていけばよいです。
計算量は、たぶんくらいです。
くらいだと間に合いますね。ただし、その分メモリを食います。

この方法ではいきなり直角三角形が一つしかないLを求められないですが、直接求める方法もあります。とすると、必ずになるので、となって、残りがです。すなわち、なら直角三角形が一つだけになります。また、のとき、なら、まずだとで残りがという直角三角形があります。とも考えられますが、これだとnが十分に大きくならないので、必ず直角三角形は一つになります。これだと、は全て成り立つので、素数の個数を数えるだけです。このようにすれば直接数えることができますが、最初の方法より速くなりませんでした。

import sys


#################### library ####################

fn gcd(n: Int, m: Int) -> Int:
    if m == 0:
        return n
    else:
        return gcd(m, n % m)


#################### List ####################

fn initialize_list[T: CollectionElement](N: Int, init: T) -> List[T]:
    var a = List[T](capacity=N)
    for n in range(N):
        a.append(init)
    return a

trait Printable(CollectionElement, Stringable):
    pass

fn print_list[T: Printable](a: List[T]):
    if a.size > 0:
        var s = "[" + str(a[0])
        for i in range(1, a.size):
            s += ", " + str(a[i])
        s += "]"
        print(s)
    else:
        print("[]")


#################### process ####################

fn f(L: Int) -> Int:
    var freq = initialize_list(L+1, 0)
    for l in range(1, L/12+1):
        var n1 = L // (2 * l)
        for m in range(2, n1):
            if m * (m + 1) > n1:
                break
            var nm0 = (m + 1) // 2 * 2 + 1
            var n2 = n1 // m
            for nm in range(nm0, min(n2+1, m*2), 2):
                if gcd(m, nm) != 1:
                    continue
                var p = 2 * l * m * nm
                freq[p] += 1
    
    var counter = 0
    for i in range(1, L+1):
        if freq[i] == 1:
            counter += 1
    return counter

fn main() raises:
    var args = sys.argv()
    var L = atol(args[1])
    print(f(L))