0 people like it.

# Integer factorization

Return a list of the prime factors for a natural number using trial division and a prime sieve. Ref: http://en.wikipedia.org/wiki/Trial_division Ref: http://fssnip.net/7D

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: ``` ``````open System open System.Collections let calculate_primes max = let array = new BitArray(max, true); let lastp = Math.Sqrt(float max) |> int for p in 2..lastp+1 do if array.Get(p) then for pm in p*2..p..max-1 do array.Set(pm, false); seq { for i in 2..max-1 do if array.Get(i) then yield i } let primes = let globalMax = 1000000 let primes = calculate_primes globalMax |> Seq.cache fun max -> Seq.takeWhile (fun p -> p <= max) primes let factor_by_trial_division n = let rec factor_by_trial_division' n primes = if n = 1 then [1] else if Seq.isEmpty primes then [n] else let p = Seq.head primes if p*p > n then [n] else if n % p = 0 then p :: factor_by_trial_division' (n/p) primes else let primes' = Seq.skip 1 primes factor_by_trial_division' n primes' factor_by_trial_division' n (primes (int(sqrt(float(n))) + 1)) ``````
namespace System
namespace System.Collections
val calculate_primes : max:int -> seq<int>

Full name: Script.calculate_primes
val max : int
Multiple items
val array : BitArray

--------------------
type 'T array = 'T []

Full name: Microsoft.FSharp.Core.array<_>
Multiple items
type BitArray =
new : length:int -> BitArray + 5 overloads
member And : value:BitArray -> BitArray
member Clone : unit -> obj
member CopyTo : array:Array * index:int -> unit
member Count : int
member Get : index:int -> bool
member GetEnumerator : unit -> IEnumerator
member IsSynchronized : bool
member Item : int -> bool with get, set
...

Full name: System.Collections.BitArray

--------------------
BitArray(length: int) : unit
BitArray(bytes: byte []) : unit
BitArray(values: bool []) : unit
BitArray(values: int []) : unit
BitArray(bits: BitArray) : unit
BitArray(length: int, defaultValue: bool) : unit
val lastp : int
type Math =
static val PI : float
static val E : float
static member Abs : value:sbyte -> sbyte + 6 overloads
static member Acos : d:float -> float
static member Asin : d:float -> float
static member Atan : d:float -> float
static member Atan2 : y:float * x:float -> float
static member BigMul : a:int * b:int -> int64
static member Ceiling : d:decimal -> decimal + 1 overload
static member Cos : d:float -> float
...

Full name: System.Math
Math.Sqrt(d: float) : float
Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
val p : int32
BitArray.Get(index: int) : bool
val pm : int32
BitArray.Set(index: int, value: bool) : unit
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
val i : int
val primes : (int -> seq<int>)

Full name: Script.primes
val globalMax : int
val primes : seq<int>
module Seq

from Microsoft.FSharp.Collections
val cache : source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.cache
val takeWhile : predicate:('T -> bool) -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.takeWhile
val p : int
val factor_by_trial_division : n:int -> int list

Full name: Script.factor_by_trial_division
val n : int
val factor_by_trial_division' : (int -> seq<int> -> int list)
val isEmpty : source:seq<'T> -> bool

Full name: Microsoft.FSharp.Collections.Seq.isEmpty
val head : source:seq<'T> -> 'T