f# - 此质因数分解代码适用于小数，但对于大数会因 OutOfMemoryException 而失败？

Question

我正在尝试获取大量的质因数..

let factors (x:int64) =
  [1L..x]
  |> Seq.filter(fun n ->  x%n = 0L)

let isPrime (x:int64) = 
 factors x
 |> Seq.length = 2

let primeFactors (x:int64)= 
 factors x 
 |> Seq.filter isPrime

这适用于 13195，但因 600851475143 的 OutOfMemoryException 而失败？

抱歉，如果我遗漏了一些明显的东西，这只是我使用 F# 的第三天，直到今天早上我才知道什么是素数。

Answer 1

表达式 [1L..x] 创建一个列表，在您的示例中，该列表太大而无法存储在内存中。

相比之下，序列是惰性的，因此如果小心使用，您可以避免计算整个中间列表。您的代码已经使用序列，但如前所述，它以列表开头，为避免从列表转换，您可以使用大括号:{1L..x}

使用序列表达式是另一种选择:

let factors (x:int64) = seq {
    for i = 1L to x do
        if x%i = 0L then yield i}

解决了 OutOfMemoryException 问题后，您的 prime 函数非常慢，您可以按照注释中的建议对其进行优化，方法是在找到 1 与其之间的除数后立即返回 false平方根。可以通过将数字除以找到的质数因子并使用质数筛来实现进一步的优化，您还可以查看一些有效的算法 here .