Project Euler Problem 3 in F#

I’m afraid your function is not doing what it suppose to do.
In your “max_factor” funciton you’re only testing numbers up to sqrt(n), but prime factors can be > that.
For example prime factors of 2010 are [2;3;5;67] but because 67 > sqrt(2010)//44.8 your function would return 5 as a max factor, which is obviously wrong.
Square root is the limit when testing if a number is prime and you can use it in the “is_prime” function instead of (i>x/2):

let isPrime x =
let rec check i =
double i > System.Math.Sqrt(double x) || (x % i 0I && check (i + 1I))
check 2I

Best regards

Good catch, Jakub. For some reason I had swapped the two limits between the two functions (and still had my algorithm working for this particular case).

I am updating the code accordingly, while also moving from BigInteger to long which is enough for this case and it’s much quicker at run time.

I really struggled with this one. This solution, and all the ones I tried, were just too slow.

I eventually found an algorithmic optimisation which both makes the code much shorter, and the execution vastly more efficient. http://basildoncoder.com/blog/2008/04/07/project-euler-problem-3/.

The basic idea is that when I find the first factor of a number (starting from 2) I’ve also found the first prime factor (otherwise one of its factors would also divide the number). So, to find the next prime factor, I divide the original number, by this prime factor, and then repeat. (yes, it’s a bit difficult to get one’s head around it, but it works).

let LargestPrimeFactor n =
let rec Aux n withLargest fromN =
if n < fromN * 2L then
(max n withLargest)
elif n % fromN = 0L then
Aux (n / fromN) (max withLargest fromN) 2L
else
Aux n withLargest (fromN + 1L)

It executes for almost instantly for 600851475143. (My other solutions never finished, before I stopped them at 15 minutes).

I skipped that last line of my solution…

Aux n 1L 2L

Thanks Stefan for your replies to my comments on problems 4 and 5!

I’m thinking that this code is probably just too difficult to read. It was certainly difficult to write. I’ll re-post it, with a few changes:

- Build a list of prime factors, instead of just finding the largest. Then one can see it working
a bit more clearly. After the list is built, use Seq.max to get the largest. (I built this version first, before the final version which extracts the largest during the intermediate work).
- Use more standard naming conventions (“i” instead of “fromN”, “acc” for the accumulator). I like the wordier versions to keep track of what I’m doing when developing.
- Add some comments
- Try to format the code.

let Problem3 n =
let rec PrimeFactors n i acc =
// Read as: Add the prime factors of n to the accumulator, given that
// 0..i – 1 are not factors.
if n Seq.max

Well, that didn’t work very well! Try again without the pre tag. I’m afraid that was my best shot at formatting it.

let Problem3 n =
let rec PrimeFactors n i acc =
// Read as: Add the prime factors of n to the accumulator, given that
// 0..i – 1 are not factors.
if n Seq.max

let Problem3 n =
let rec PrimeFactors n i acc =
// Read as: Add the prime factors of n to the accumulator, given that
// 0..i – 1 are not factors.
if n Seq.max

let Problem3 n =
let rec PrimeFactors n i acc =
// Read as: Add the prime factors of n to the accumulator, given that
// 0..i – 1 are not factors.
if n Seq.max

Same problem solved in C#

https://sites.google.com/site/eulerproblemsincsharp/home/problem-3