使用相同的代码计算质因数会产生不同的结果？

Question

我基本上是在尝试计算 BigInteger 的素数因子，我有两个简单的因式分解函数，它们看起来应该按照我在下面使用它们的方式产生相同的结果，但这是这里不是这种情况，有人可以解释发生了什么吗？

let lookupTable = new HashSet<int>(primes)

let isPrime x = lookupTable.Contains x

let factors (n:bigint) = 
    Seq.filter (fun x -> n % x = 0I) [1I..n]

let factors' (n:bigint) = 
    Seq.filter (fun x -> n % x = 0I) [1I..bigint(sqrt(float(n)))]


600851475143I
|> fun n -> bigint(sqrt(float(n)))
|> factors
|> Seq.map int
|> Seq.filter isPrime
|> Seq.max // produces 137

600851475143I
|> factors'
|> Seq.map int
|> Seq.filter isPrime
|> Seq.max // produces 6857 (the right answer)

Answer 1

你们的功能不等价。在第一个函数中，候选列表转到n，过滤函数也使用n进行余数计算。然而，第二个函数也使用 n 进行余数计算，但候选列表改为 sqrt(n)。

要使第二个函数等效，您需要重新表述如下：

let factors' (n:bigint) = 
    let k = bigint(sqrt(float(n)))
    Seq.filter (fun x -> k % x = 0I) [1I..k]

更新，澄清一下：
在上面的代码中，请注意 k 是如何在两个地方使用的：生成初始候选列表和计算过滤器函数中的余数？这正是我对您的代码所做的更改：我的代码在两个地方都使用 k，但是您的代码在一个地方使用 k，而在另一个地方使用 n。

这是您的原始函数在 k:

下的样子

let factors' (n:bigint) = 
    let k = bigint(sqrt(float(n)))
    Seq.filter (fun x -> n % x = 0I) [1I..k]

注意它如何在一处使用 k，而在另一处使用 n。

使用相同的代码计算质因数会产生不同的结果？

computing prime factors using same code produces different results?

primes

f#

biginteger