-
-
Save Sehnsucht-Fr/d30d66b5e2acbe3665ed to your computer and use it in GitHub Desktop.
Finding Prime Factors in F# (http://www.markheath.net/post/finding-prime-factors-in-f)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
let factorize number = | |
if number < 2 then Seq.empty | |
else | |
Some (1, 2, number) | |
|> Seq.unfold (Option.bind (fun (increment, factor, number) -> | |
if number < pown factor 2 then | |
Some (Some number, None) | |
elif number % factor = 0 then | |
Some (Some factor, Some (increment, factor, number / factor)) | |
else | |
Some (None, Some (2, factor + increment, number)))) | |
|> Seq.choose id |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
open LanguagePrimitives | |
let inline factorize number = | |
let two = GenericOne + GenericOne | |
let rec factorize increment factor number = seq { | |
if number % factor = GenericZero then | |
yield factor | |
if number <> factor then | |
yield! factorize increment factor <| number / factor | |
// Parse will fail if given a floating number with decimal part (502798. will pass but not 502798.1) | |
elif bigint.Parse <| string number > pown (bigint.Parse <| string factor) 2 then | |
yield! factorize two <| factor + increment <| number | |
else | |
yield number | |
} | |
factorize GenericOne two number |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment