0 people like it.
Like the snippet!

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 IsReadOnly : bool
  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

Full name: Microsoft.FSharp.Collections.Seq.head

val primes' : seq<int>

val skip : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.skip

val sqrt : value:'T -> 'U (requires member Sqrt)

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

Raw view Test code New version

More information

Link:	http://fssnip.net/83
Posted:	13 years ago
Author:	d95danb
Tags:	primes factorization math