MojoでProject Euler 51

https://projecteuler.net/problem=51

素数が8つ以上だと、マスクしている数字は3の倍数個でないといけません。なぜなら、そうでなければ数字ごとに3の剰余が変わってしまうから、最大10個できる整数のうち3個は3の倍数になってしまうからです。
素数9つはすぐに出てきましたが、10個は出てきませんね。

import sys


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

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

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

fn insert_list[T: CollectionElement](inout v: List[T], e: T, i: Int):
    v.append(e)
    for k in range(len(v) - 1, i, -1):
        v[k] = v[k-1]
    v[i] = e

fn combinations_core[T: CollectionElement](a: List[T],
                                            n: Int, k: Int) -> List[List[T]]:
    if n == 0:
        return List[List[T]](List[T]())
    
    var vs = List[List[T]]()
    for k1 in range(k, len(a) - n + 1):
        var v = combinations_core(a, n-1, k1+1)
        for w in v:
            insert_list(w[], a[k1], 0)
            vs.append(w[])
    return vs

fn combinations[T: CollectionElement](a: List[T], n: Int) -> List[List[T]]:
    return combinations_core(a, n, 0)

fn range_list(first: Int, last: Int, delta: Int) -> List[Int]:
    var v = List[Int]()
    if (first < last and delta > 0) or (first > last and delta < 0):
        for n in range(first, last, delta):
            v.append(n)
    return v

fn reverse_list[T: CollectionElement](a: List[T]) -> List[T]:
    var b = List[T]()
    for i in range(len(a) - 1, -1, -1):
        b.append(a[i])
    return b


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

fn make_prime_table(N: Int) -> List[Bool]:
    var a = initialize_list(N+1, True)
    for p in range(2, N+1):
        if p * p > N:
            break
        elif not a[p]:
            continue
        
        for n in range(p*p, N+1, p):
            a[n] = False
    return a

fn digits(owned n: Int) -> List[Int]:
    var ds = List[Int]()
    while n > 0:
        var d = n % 10
        ds.append(d)
        n //= 10
    return ds

fn number(ds: List[Int]) -> Int:
    var n = 0
    for d in ds:
        n = n * 10 + d[]
    return n


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

fn fill(d: Int, mask: List[Int], ds: List[Int]) -> Int:
    var L1 = len(mask)
    var L2 = len(ds)
    var new_ds = List[Int]()
    var k = 0
    var l = 0
    for i in range(0, L1 + L2):
        if mask[k] == i:
            new_ds.append(d)
            k += 1
        else:
            new_ds.append(ds[l])
            l += 1
    return number(reverse_list(new_ds))

fn collect_primes(mask: List[Int], n: Int, primes: List[Bool]) -> List[Int]:
    var ds = digits(n)
    var E = len(mask) + len(ds)
    var ps = List[Int]()
    for d in range(10):
        if d == 0 and mask[len(mask)-1] == E - 1:
            continue
        var n = fill(d, mask, ds)
        if primes[n]:
            ps.append(n)
    return ps

fn f_each(M: Int, E: Int) -> Int:
    var N = 10**E
    var primes = make_prime_table(N)
    var a = range_list(1, E, 1)
    var min_prime = -1
    for num_mask in range(3, E, 3):
        for mask in combinations(a, num_mask):
            var first = 10**(E-num_mask-1) + 1
            var last = (first - 1) * 10
            for n in range(first, last, 2):
                var ps = collect_primes(mask[], n, primes)
                if len(ps) != M:
                    continue
                if min_prime == -1 or ps[0] < min_prime:
                    min_prime = ps[0]
                    print_list(ps)
    return min_prime

fn f(M: Int) -> Int:
    var E = 4
    while True:
        var ret = f_each(M, E)
        if ret != -1:
            return ret
        E += 1

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