вычисление простых коэффициентов с использованием одного и того же кода дает разные результаты?

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] 

Update, чтобы прояснить этот вопрос несколько:
В приведенном выше коде, обратите внимание, как 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 в другой.