Skip to content

Instantly share code, notes, and snippets.

@aktowns
Created November 21, 2010 11:29
Show Gist options
  • Save aktowns/708667 to your computer and use it in GitHub Desktop.
Save aktowns/708667 to your computer and use it in GitHub Desktop.
(*
Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
*)
let rec find_factors (count, target, list) =
if count < 2L then (1L,target,count::list)
else if (target % count = 0L) then find_factors((count-1L), target, count::list)
else find_factors((count-1L),target, list)
let rec is_prime number =
let _,_,list = find_factors (number,number,[])
let output = List.fold (+) 0L list
(output = (number + 1L))
let _,_,factors = find_factors (600851475143L,600851475143L,[])
factors
|> List.rev
|> List.filter (fun n -> (n%2L) > 0L || (n%5L) > 0L)
|> List.filter (fun n -> is_prime n)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment