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

Previous Version Raw view Test code New version

More information

Link:	http://fssnip.net/8N
Posted:	14 years ago
Author:	Arjen Kopinga
Tags:	primes , sieve , eratosthenes , algorithms