Seq.find crashes for large numbers (int64)

user_52444 0
Viewed 128

I have the following F# code, which should find the smallest prime factor of a given number x:

let smallestFactor x : int64 = 
    [2L .. x] |> Seq.find( fun s -> x % s = 0L )

However, when I call the function with a large number, e.g. 600851475143 my Visual Studio takes some GB of memory and all CPU power and never returns. I start the code via JetBrains ReSharper as a unit test which is written in C#:

[Test]
public void SmallestFactorOf600851475143()
{
    var result = Problem3.smallestFactor( 600851475143 );
}

My F# code and the number are part of a solution for problem 3, Euler Project

I am just starting with F#. Is there an obvious problem with my code?

sequence f#
1 Answers

Well, as already mentioned, expression [2L .. x] creates list, and for x = 600851475143 it allocates 600851475143 * 8 ~ 4,806 GB, so that's why it doesn't works. What you do really want, is to iterate through all numbers, so sequence will work perfectly for you:

let smallestFactor x : int64 = 
    seq {2L .. x} |> Seq.find( fun s -> x % s = 0L )
user_103097740
Related