MojoでProject Euler 23

https://projecteuler.net/problem=23

素直に23111までの過剰数を求めて総当たりします。

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)


#################### 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 is_enough_each(r: Int, table: DynamicVector[Int]) -> Bool:
    for i in range(r, table.size, 6):
        if table[i] > i * 2:
            return True
    return False

fn make_abundant_list(M: Int) -> DynamicVector[Int]:
    var ns = DynamicVector[Int]()
    try:
        var table = make_sum_divisors_table(M)
        for n in range(12, M):
            if table[n] > n * 2:
                ns.push_back(n)
    except:
        pass
    return ns

fn f() raises -> Int:
    var N = 28123
    var ab_list = make_abundant_list(N-12)
    var bs = DynamicVector[Bool]()
    for _ in range(N+1):
        bs.push_back(False)
    
    for i in range(ab_list.size):
        var ab1 = ab_list[i]
        for j in range(i, ab_list.size):
            var ab2 = ab_list[j]
            var n = ab1 + ab2
            if n > N:
                break
            bs[n] = True
    
    var s = 0
    for n in range(1, N+1):
        if not bs[n]:
            s += n
    return s

fn main() raises:
    print(f())