In the pursuit of learning F#, I have been working through some Project Euler problems.
This is my solution for problem 3:
open System open System.Collections.Generic let number = 600851475143L let limit = Convert.ToInt32(sqrt (float number)) let sieve = Array.create (limit+1) true sieve.SetValue(false,0) sieve.SetValue(false,1) let rec markNotPrime prime multiple = if multiple > limit then prime else sieve.SetValue(false, multiple) let nm = prime+multiple markNotPrime prime nm let smallPrimes = Seq.unfold(fun a -> Some(a, (a+1))) 2 |> Seq.takeWhile(fun a -> a <= limit) |> Seq.filter( fun a -> sieve.[a]) |> Seq.map( fun a -> let b = a+a markNotPrime a b) |> Seq.filter( fun a -> number % (int64 a) = 0L) let bigPrimes = new List<int>() let rec addBigPrime potentialPrime = match potentialPrime with | p when bigPrimes.Contains(potentialPrime) -> ignore() | p when smallPrimes |> Seq.forall(fun a -> (potentialPrime % a) <> 0) -> bigPrimes.Add(p) | _ -> smallPrimes |> Seq.filter(fun a -> (potentialPrime % a) = 0) |> Seq.iter(fun a -> addBigPrime (potentialPrime / a)) smallPrimes |> Seq.map(fun a -> (int (number/(int64 a)))) |> Seq.iter(addBigPrime) let answer = smallPrimes |> Seq.append(bigPrimes) |> Seq.max printfn "smallPrimes: %A" smallPrimes printfn "bigPrimes: %A" bigPrimes printfn "answer: %d" answer
I am aware of how simply this could have been done, but I was trying to do this in a vacuum as much as possible.
I am new to both prime factorization and F#; however, I am really only looking for comments on F#, not how poorly my factorization algorithm works (I know it's bad) i.e. what style mistakes am I making, or how the code could be made more functional.
Of particular interest, where do you think I am missing the mark entirely?
After thinking more about my solution overnight, I had more thought about exactly what my solution was doing, and why the simpler methods are so much simpler.
During my research on factoring primes, I think I got too caught up in the sieve of Eratosthenes, and didn't focus on the actual problem.
What I should have been trying to do:
- Search for the smallest prime factor
- Once found save it to the list of prime factors
- Divide this factor out of the number to be factored
- Repeat from step 1 substituting the number to be factored with the quotient from step 3, and start the search from the prime factor found in step 2.
- Get the biggest prime from the list.
What I actually did:
- Search for all prime numbers from 2 to the square root of the number to be factored.
- During the search, check each prime to see if it divides evenly.
- Once complete divide each of these "small primes" to generate a list potential big primes.
- Divide each of the big primes by all of the small primes as a test for primality.
- Combined the lists, and get the biggest one.