MojoでProject Euler 26

https://projecteuler.net/problem=26

各に対し、となる最小の自然数を求めます。オイラーの定理からなので、の約数となります。
実際のところは、素数の大きい方から順に調べて、周期がその数より1小さいものがあれば、その素数が求める答えです。

from math import min
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)

def pow(b: Int, e: Int, d: Int) -> Int:
    if e == 1:
        return b % d
    elif e % 2 == 1:
        return b * pow(b, e-1, d) % d
    else:
        var p = pow(b, e//2, d)
        return p * p % d

fn print_vector(v: DynamicVector[Int]):
    for k in range((v.size + 9) // 10):
        var s = str("")
        for i in range(k*10, min(k*10+10, v.size)):
            s += str(v[i]) + " "
        print(s)


#################### 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 __mul__(self, other: Factors) -> Factors:
        var fs = DynamicVector[Tuple[Int, Int]]()
        var L1 = self.fs.size
        var L2 = other.fs.size
        var k = 0
        var l = 0
        while k < L1 and l < L2:
            var p1 = self.fs[k].get[0, Int]()
            var p2 = other.fs[l].get[0, Int]()
            var e1 = self.fs[k].get[1, Int]()
            var e2 = other.fs[l].get[1, Int]()
            if p1 == p2:
                fs.push_back((p1, e1+e2))
                k += 1
                l += 1
            elif p1 < p2:
                fs.push_back((p1, e1))
                k += 1
            else:
                fs.push_back((p2, e2))
                l += 1
        
        for k1 in range(k, L1):
            fs.push_back(self.fs[k1])
        for l1 in range(l, L2):
            fs.push_back(other.fs[l1])
        return Factors(fs)
    
    @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)


#################### PrimeTable ####################

struct PrimeTable:
    var table: DynamicVector[Int]
    
    fn __init__(inout self, table: DynamicVector[Int]):
        self.table = table
    
    fn factorize(self, n: Int) -> Factors:
        try:
            return Factors(self.factorize_core(n))
        except:
            return Factors(DynamicVector[Tuple[Int, Int]]())
    
    fn factorize_core(self, n: Int) raises -> DynamicVector[Tuple[Int, Int]]:
        if n == 1:
            return DynamicVector[Tuple[Int, Int]]()
        
        var p = self.table[n]
        var a = div_pow(n, p)
        var e = a.get[0, Int]()
        var m = a.get[1, Int]()
        var fs = DynamicVector[Tuple[Int, Int]]()
        fs.push_back((p, e))
        var fs1 = self.factorize_core(m)
        for f in fs1:
            fs.push_back(f[])
        return fs
    
    @staticmethod
    def make_min_prime_table(N: Int) -> PrimeTable:
        var a = DynamicVector[Int]()
        for i in range(N+1):
            a.push_back(1)
        
        for p in range(2, N+1):
            if p*p > N:
                break
            if a[p] != 1:
                continue
            for n in range(p, N+1, p):
                if a[n] == 1:
                    a[n] = p
        
        for n in range(2, N+1):
            if a[n] == 1:
                a[n] = n
        return PrimeTable(a)


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

fn remove25(n: Int) -> Int:
    var m = n
    while m % 2 == 0:
        m //= 2
    while m % 5 == 0:
        m //= 5
    return m

fn phi(fs: Factors) -> Int:
    var m = 1
    for f in fs.fs:
        var p = f[].get[0, Int]()
        var e = f[].get[1, Int]()
        m *= (p-1) * p**(e-1)
    return m

fn period(n: Int, table: PrimeTable) raises -> Int:
    var n1 = remove25(n)
    if n1 == 1:
        return 0
    
    var fs1 = table.factorize(n1)
    var n2 = phi(fs1)
    var fs2 = table.factorize(n2)
    var n3 = n2
    for f2 in fs2.fs:
        var p2 = f2[].get[0, Int]()
        var e2 = f2[].get[1, Int]()
        for e in range(e2-1, -1, -1):
            n3 //= p2
            if pow(10, n3, n1) != 1:
                n3 *= p2
    return n3

fn make_period_table(N: Int) raises -> DynamicVector[Int]:
    var table = PrimeTable.make_min_prime_table(N)
    var periods = DynamicVector[Int]()
    periods.push_back(0)
    periods.push_back(0)
    for n in range(2, N+1):
        periods.push_back(period(n, table))
    return periods

fn max_arg(a: DynamicVector[Int]) -> Int:
    var max_element = a[0]
    var index = 0
    for i in range(1, a.size):
        if a[i] > max_element:
            max_element = a[i]
            index = i
    return index

fn f(N: Int) raises -> Int:
    var periods = make_period_table(N)
    return max_arg(periods)

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