algorithm - F# 中的质因数

Question

我正在努力学习 F#。
我写了一个分解素数的函数。

let PrimeFactors x =
  let rec PrimeFactorsRecursive x div list =
     if x % div = 0 then PrimeFactorsRecursive (x/div) div list @ [div]
     elif div > int(System.Math.Sqrt(float(x))) then 
       if x > 1 then list @ [x]
       else list
     else PrimeFactorsRecursive x (div + 1) list
  PrimeFactorsRecursive x 2 []

现在我不确定这是一个好的 F# 函数还是更像是“用 f# 编写的 c#”。

是否有一种“更”实用的方式来编写这段代码？

Answer 1

代码中的主要问题是您使用 @ 连接两个列表。连接两个列表花费线性时间，而不是常数时间。

常用的方法是使用 :: 运算符将新素数添加到列表的头部，如下所示:

let primeFactors x = 
    let rec fact x div list = 
        if x % div = 0 then
            fact (x/div) div (div::list)
        elif div > int(sqrt (float x)) then
            if x > 1 then x::list
            else list
        else
            fact x (div+1) list
    fact x 2 []

此外，let 绑定(bind)值通常遵循 camleStyle 命名转换。