函数式语言中的质因数分解

Question

我正在用 OCaml 编写，试图提供（某种程度上）高效的质因数分解实现。我认为 2 或更多数字的最佳表示是在指数列表中。为了简单起见，我将按素数的降序进行。所以 2 是 [1]，3 是 [1;0]，4 是 [2]，5 是 [1;0;0]。

我正在考虑使用筛法取一个数字 n 并寻找 2 到 sqrt(n) 之间所有可能的约数。然后除以任何除数并递归。然而，我能想到的每一个实现似乎都涉及重复搜索列表，这似乎是不必要的低效。我的解决方案的概要最好在这段代码中说明

let rec pf n =
  if (n=2) then ([1], 0)
  else let sq = int_of_float ( (float_of_int n) ** 0.5 ) in
  let primes = getPrimes sq in
  match earliestDiv n primes with
  | None -> n::(zero_list (n-1))
  | Some (x, i) -> let subproblem pf (n/x) in
              increment subproblem i

这里的辅助函数是：

getPrimes 它接受一个 int 和 returns 一个小于或等于它的所有素数的列表。
earliestDiv 接受一个整数 n 和整数列表 lst，returns 一个 int*int 选项对应于 [=16= 中最早的数字] 除 n。那将是元组的第一个坐标；第二个坐标将 return 这个素数 x 在素数列表中的索引。
increment 将采用一个 int 列表和索引，并将位于索引处的数字增加 1。

所有这些辅助函数都在不断地创建列表、传递列表等等。事实上，我经常觉得我在做函数式编程。我经常觉得我在不必要地遍历列表，而在命令式语言中我会编写更高效的代码。也许它只是在我的脑海里，当用命令式语言编写时，我很少注意到有多少资源进入了我使用的一些列表操作。但是，如果我遗漏了一些可以防止重复扫描列表的重要技术，我很想听听。

问题：是否需要反复创建和迭代列表才能编写此函数？

Answer 1

如果您最终为列表建立索引，或者用默认元素填充列表直到达到固定大小，则列表很可能是错误的数据结构。对于质因数分解，您可能需要一个稀疏数组的实现。地图将是比 fixed-size 列表更好（如果不是最佳）的实现。

函数式语言中的质因数分解

Prime factorization in a functional language

primes

ocaml

functional-programming

prime-factoring