MojoでProject Euler 41

https://projecteuler.net/problem=41

nが9でも8でも1～nのpandigitalは9で割り切れるから、n=7を考えればよいので、10⁷までエラトステネスの篩をして、上からpandigitalで素数のものを探せばよいです。
ただ、一般の進法を考えると、Millar-Rabinを使えばよいでしょう。その場合はどうなるでしょう。例えばB進法と考えると、自然数は

と表されるから、ある自然数dでBを割って1余るなら、dで割った余りが各桁の和をdで割った余りと同じになって、この和はnだけで決まるのでこの余りが0ならn桁のB進自然数は素数でないことになります（nが小さいときはちょっと怪しいですが）。
こうやって計算量を減らすことができますが、すぐにオーバーフローしてしまうのであまり大きなBでは計算できません。ちゃんと計算できるのはB=19までっぽいです。

import sys


#################### prime number ####################

fn add(a: Int, b: Int, d: Int) -> Int:
    var c = a + b
    if c < 0:   # overflow
        c -= d
    elif c >= d:
        c -= d
    return c

fn mul2(a: Int, b: Int, d: Int, e1: Int, e2: Int) -> Int:
    var n = 0
    var a1 = a
    for i in range(0, e2, e1):
        var b1 = (b >> i) & ((1 << e1) - 1)
        n += a1 * b1 % d
        a1 = (a1 << e1) % d
    return n % d

fn mul3(a: Int, b: Int, d: Int, e1: Int, e2: Int) -> Int:
    var n = 0
    var a1 = a
    for i in range(0, e2, e1):
        var b1 = (b >> i) & ((1 << e1) - 1)
        n = add(n, a1 * b1 % d, d)
        a1 = (a1 << e1) % d
    return n

fn mul4(a: Int, b: Int, d: Int) -> Int:
    var n = 0
    var a1 = a
    for i in range(0, 63):
        var b1 = (b >> i) & 1
        if b1 == 1:
            n = add(n, a1, d)
        a1 = add(a1, a1, d)
    return n

fn mul(a: Int, b: Int, d: Int) -> Int:
    if d < 1 << 31:
        return a * b % d
    elif d < 1 << 40:
        var b1 = b & ((1 << 20) - 1)
        var b2 = b >> 20
        var n1 = a * b1
        var n2 = (a * b2 % d) << 20
        return (n1 + n2) % d
    elif d < 1 << 45:
        return mul2(a, b, d, 15, 45)
    elif d < 1 << 48:
        return mul2(a, b, d, 12, 48)
    elif d < 1 << 50:
        return mul2(a, b, d, 10, 50)
    elif d < 1 << 54:
        return mul3(a, b, d, 6, 54)
    elif d < 1 << 55:
        return mul3(a, b, d, 5, 55)
    elif d < 1 << 56:
        return mul3(a, b, d, 4, 56)
    elif d < 1 << 57:
        return mul3(a, b, d, 3, 57)
    elif d < 1 << 60:
        return mul3(a, b, d, 2, 60)
    else:
        return mul4(a, b, d)

fn pow(n: Int, e: Int, d: Int) -> Int:
    if e == 0:
        return 1
    elif e == 1:
        return n
    elif (e & 1) == 1:
        return mul(n, pow(n, e-1, d), d)
    else:
        var m = pow(n, e>>1, d)
        return mul(m, m, d)

fn Miller_test(n: Int, owned d: Int, a: Int) -> Bool:
    var y = pow(a, d, n)
    if y == 1:
        return True
    d <<= 1
    while d < n:
        if y == n - 1:
            return True
        y = mul(y, y, n)
        d <<= 1
    return False

fn Miller_Rabin(n: Int) -> Bool:
        var d = (n - 1) >> 1
        while (d & 1) == 0:
            d >>= 1
        
        if not Miller_test(n, d, 2):
            return False
        if not Miller_test(n, d, 3):
            return False
        if not Miller_test(n, d, 5):
            return False
        if not Miller_test(n, d, 7):
            return False
        if not Miller_test(n, d, 11):
            return False
        if not Miller_test(n, d, 13):
            return False
        if not Miller_test(n, d, 17):
            return False
        return True

fn is_prime(n: Int) -> Bool:
    if n == 2:
        return True
    elif (n & 1) == 0 or n == 1:
        return False
    else:
        for p in range(3, 20, 2):
            if p * p > n:
                return True
            elif n % p == 0:
                return False
        
        return Miller_Rabin(n)


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

trait Printable(CollectionElement, Stringable):
    pass

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 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 copy_list[T: CollectionElement](a: List[T]) -> List[T]:
    return sublist(a, 0, len(a))

fn sublist[T: CollectionElement](a: List[T], first: Int, last: Int) -> List[T]:
    var b = List[T]()
    for i in range(first, last):
        b.append(a[i])
    return b

fn add_list[T: CollectionElement](a: List[T], b: List[T]) -> List[T]:
    var c = List[T]()
    for e in a:
        c.append(e[])
    for e in b:
        c.append(e[])
    return c

fn extend_list[T: CollectionElement](inout a: List[T], b: List[T]):
    for e in b:
        a.append(e[])

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

fn permutations[T: CollectionElement](owned i: Int, v: List[T]) -> List[T]:
    var n = len(v)
    
    var w = copy_list(v)
    var rs = List[Int]()
    for k in range(2, n+1):
        var r = i % k
        i //= k
        rs.append(r)
    
    for k in range(0, n-1):
        var r = rs[n-k-2]
        if r == 0:
            continue
        var tmp = w[k]
        w[k] = w[k+r]
        for j in range(k+r, k+1, -1):
            w[j] = w[j-1]
        w[k+1] = tmp
    
    return w

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

fn str_num(owned n: Int, B: Int) -> String:
    var s: String = ""
    while n > 0:
        var d = n % B
        if d < 10:
            s = chr(d + 48) + s
        else:
            s = chr(d + 87) + s
        n //= B
    return s


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

fn is_all_not_prime(n: Int, B: Int) -> Bool:
    var s = n * (n + 1) // 2
    for d in range(2, B):
        if (B - 1) % d == 0 and s % d == 0:
            return True
    else:
        return False

fn factorial(n: Int) -> Int:
    return 1 if n == 0 else n * factorial(n - 1)

fn f_each(n: Int, B: Int) -> Int:
    var v = List[Int]()
    for d in range(n, 0, -1):
        v.append(d)
    
    for i in range(factorial(n)):
        var ds = permutations(i, v)
        var n = number(ds, B)
        if is_prime(n):
            return n
    
    return 0

fn f(B: Int) -> Int:
    for n in range(B-1, 1, -1):
        if is_all_not_prime(n, B):
            continue
        var p = f_each(n, B)
        if p > 0:
            return p
    return 0

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