这个素数分解代码适用于小数字,但是对于大数字而言失败并出现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

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

相反的序列是懒惰的,因此如果小心使用,您可以避免计算整个中间列表.您的代码已经使用了序列,但正如它在列表开头之前所说的那样,为了避免从列表转换,您可以使用大括号:{1L..x}

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

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

解决了这个OutOfMemoryException问题后,你的素数函数非常慢,你可以按照注释中的建议优化它,false在找到1和它的平方根之间的除数后立即返回.进一步优化可以通过将数字除以找到它们的素数因子并使用筛子作为素数来实现,您还可以在这里查看一些有效的算法.