https://projecteuler.net/problem=88
たくさんの素数から合成された数のほうがkが大きくなるのは明らかですが、小さい数から順に分解してkを求めるしかなさそうですね。
Mojoで謎のエラーが出て苦戦しました。次のように素因数分解構造体を次のようにするとどうしてもうまくいきません。
@value struct Pair[T: CollectionElement, U: CollectionElement]: var x: T var y: U alias Factor = Pair[Int, Int] @value struct Factors(Comparable): var fs: List[Factor] var value: Int
以下のようにしたらすんなり動きました。
from math import sqrt import sys #################### List #################### 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 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 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 connect_list[T: CollectionElement](a: List[T], b: List[T]) -> List[T]: var a1 = copy_list(a) a1.extend(b) return a1 #################### Pair #################### @value struct Pair[T: CollectionElement, U: CollectionElement]: var x: T var y: U #################### Factors #################### alias Factor = Pair[Int, Int] @value struct Factors(Comparable): var ps: List[Int] var es: List[Int] var value: Int fn __len__(self) -> Int: return len(self.ps) fn __lt__(self, other: Self) -> Bool: return self.value < other.value fn __le__(self, other: Self) -> Bool: return self.value <= other.value fn __eq__(self, other: Self) -> Bool: return self.value == other.value fn __ne__(self, other: Self) -> Bool: return self.value != other.value fn __gt__(self, other: Self) -> Bool: return self.value > other.value fn __ge__(self, other: Self) -> Bool: return self.value >= other.value fn is_prime(self) -> Bool: return len(self.ps) == 1 and self.es[0] == 1 @staticmethod fn divide_vec(es: List[Int]) -> List[List[Int]]: var L = len(es) var ess = List[List[Int]]() if L == 1: for e1 in range(es[0]+1): ess.append(List[Int](e1)) else: var mid = L // 2 var ess1 = Factors.divide_vec(sublist(es, 0, mid)) var ess2 = Factors.divide_vec(sublist(es, mid, L)) for es1 in ess1: for es2 in ess2: ess.append(connect_list(es1[], es2[])) return ess fn divide(self) -> List[Pair[Factors, Factors]]: var pairs = List[Pair[Factors, Factors]]() for es1_ in Factors.divide_vec(self.es): var ps1 = List[Int]() var ps2 = List[Int]() var es1 = List[Int]() var es2 = List[Int]() var value1 = 1 var value2 = 1 for i in range(len(self.ps)): var p = self.ps[i] var e1 = es1_[][i] var e2 = self.es[i] - e1 if e1 != 0: ps1.append(p) es1.append(e1) value1 *= p**e1 if e2 != 0: ps2.append(p) es2.append(e2) value2 *= p**e2 pairs.append(Pair[Factors, Factors](Factors(ps1, es1, value1), Factors(ps2, es2, value2))) return pairs @staticmethod fn make_min_factor_table(N: Int) -> List[Int]: var a = List[Int]() for n in range(N+1): a.append(n) for p in range(2, N+1): if p*p > N: break if a[p] != p: continue for n in range(p*p, N+1, p): if a[n] == n: a[n] = p return a @staticmethod fn factorize(n: Int, table: List[Int]) -> Factors: var m = n var ps = List[Int]() var es = List[Int]() var p = table[m] ps.append(p) es.append(1) m //= p while m > 1: p = table[m] if p == ps[len(ps)-1]: es[len(ps)-1] += 1 else: ps.append(p) es.append(1) m //= p return Factors(ps, es, n) #################### process #################### fn divide(fs: Factors) -> List[List[Int]]: var dss = List[List[Int]](List[Int](fs.value)) for pair in fs.divide(): var fs1 = pair[].x var fs2 = pair[].y if fs1.value == 1 or fs1.value > fs2.value: continue elif fs1.value <= fs2.value < fs1.value**2: dss.append(List[Int](fs1.value, fs2.value)) else: for ds2 in divide(fs2): if fs1.value <= ds2[][0]: var ds = connect_list(List[Int](fs1.value), ds2[]) dss.append(ds) return dss fn calc_k(ds: List[Int], owned n: Int) -> Int: for d in ds: n -= d[] return n + len(ds) fn f(N: Int) -> Int: var table = initialize_list(N+1, 0) var factor_table = Factors.make_min_factor_table(N*2) var set_ks = Set[Int]() for n in range(4, N*2+1): var fs = Factors.factorize(n, factor_table) if fs.is_prime(): continue for ds in divide(fs): if len(ds[]) == 1: continue var k = calc_k(ds[], n) if k <= N and table[k] == 0: table[k] = n set_ks.add(k) if len(set_ks) == N - 1: break var s: Int = 0 var used = Set[Int]() for k in range(2, N+1): var n = table[k] if n not in used: s += n used.add(n) return s fn main() raises: var args = sys.argv() var N = atol(args[1]) print(f(N))
