MojoでProject Euler 21

https://projecteuler.net/problem=21

約数の和はエラトステネスのふるいのようにまとめて求められますが、元々の値をオーバーしたら個別に素因数分解して求めます。

import sys


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

def div_pow(n: Int, d: Int) -> Tuple[Int, Int]:
    var m = n
    var e = 0
    while m % d == 0:
        e += 1
        m //= d
    return (e, m)


#################### Factors ####################

struct Factors(CollectionElement):
    var fs: DynamicVector[Tuple[Int, Int]]
    
    fn __init__(inout self, fs: DynamicVector[Tuple[Int, Int]]):
        self.fs = fs
    
    fn __copyinit__(inout self, other: Factors):
        self.fs = other.fs
    
    fn __moveinit__(inout self, owned other: Factors):
        self.fs = other.fs^
    
    fn sum_divisors(self) -> Int:
        var m = 1
        for a in self.fs:
            var p = a[].get[0, Int]()
            var e = a[].get[1, Int]()
            var m1 = 1
            for _ in range(e):
                m1 = m1 * p + 1
            m *= m1
        return m
    
    @staticmethod
    fn create(n: Int) raises -> Factors:
        var fs = DynamicVector[Tuple[Int, Int]]()
        var m = n
        for p in range(2, n+1):
            if p*p > m:
                break
            elif m%p == 0:
                var a = div_pow(m, p)
                var e = a.get[0, Int]()
                fs.push_back((p, e))
                m = a.get[1, Int]()
        if m > 1:
            fs.push_back((m, 1))
        return Factors(fs)


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

def make_sum_divisors_table(N: Int) -> DynamicVector[Int]:
    var a = DynamicVector[Int]()
    var b = DynamicVector[Int]()
    for i in range(N):
        a.push_back(i)
        b.push_back(1)
    
    for p in range(2, N):
        if p*p > N:
            break
        if a[p] == 1:
            continue
        for n in range(p, N, p):
            m = 1
            while a[n] % p == 0:
                m = m * p + 1
                a[n] /= p
            b[n] *= m
    
    for n in range(2, N):
        if a[n] != 1:
            b[n] *= a[n] + 1
    return b

fn f(N: Int) raises -> Int:
    var s = 0
    var table = make_sum_divisors_table(N)
    for n in range(2, N):
        var m = table[n] - n
        var s1 = table[m] if m < N else Factors.create(m).sum_divisors()
        if n == s1 - m and n != m:
            s += n
    return s

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