4 people like it.
Like the snippet!
A fast sieve of Eratosthenes
A prime Eratosthenes' sieve, using a bit array and sieving only odd composites to conserve memory and keep things fast.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
|
open System
open System.Collections
let getPrimes nmax =
let sieve = new BitArray((nmax/2) + 1, true)
let result = new ResizeArray<int>(nmax / 10)
let upper = int (sqrt (float nmax))
if nmax > 1 then result.Add(2)
let mutable m = 1
while 2 * m + 1 <= nmax do
if sieve.[m] then
let n = 2 * m + 1
if n <= upper then
let mutable i = m
while 2 * i < nmax do sieve.[i] <- false; i <- i + n
result.Add n
m <- m + 1
result
|
namespace System
namespace System.Collections
val getPrimes : nmax:int -> ResizeArray<int>
Full name: Script.getPrimes
val nmax : int
val sieve : BitArray
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 result : ResizeArray<int>
type ResizeArray<'T> = Generic.List<'T>
Full name: Microsoft.FSharp.Collections.ResizeArray<_>
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 upper : int
val sqrt : value:'T -> 'U (requires member Sqrt)
Full name: Microsoft.FSharp.Core.Operators.sqrt
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<_>
Generic.List.Add(item: int) : unit
val mutable m : int
val n : int
val mutable i : int
More information