MojoでProject Euler 72

https://projecteuler.net/problem=72

分母を固定すれば、

を計算すればよいとわかります。頑張れば速くできる気がしますが、ふつうにふるいを使います。

import sys


#################### 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("[]")


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

fn make_phi_table(N: Int) -> List[Int]:
    var a = List[Int]()
    for n in range(N+1):
        a.append(n)
    var b = initialize_list(N+1, 1)
    b[0] = 0
    b[1] = 0
    for p in range(2, N+1):
        if p * p > N:
            break
        if a[p] != p:
            continue
        for n in range(p, N+1, p):
            var e = 1
            a[n] //= p
            b[n] *= p - 1
            while a[n] % p == 0:
                e += 1
                a[n] //= p
                b[n] *= p
    
    for n in range(2, N+1):
        if a[n] != 1:
            b[n] *= a[n] - 1
    return b


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

fn f(N: Int) -> Int:
    var table = make_phi_table(N)
    var s = 0
    for phi in table:
        s += phi[]
    return s

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