3 people like it.

Simple Sieve of Eratosthenes with sets

Simple implementation of the Sieve of Eratosthenes with set arithmetic. 

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 

(*
Sieve of Eratosthenes.
*)

let generatePrimes limit =
    let candidates = set [ 2 .. limit ]
    let bases = [| 2 .. (limit / 2 + 1) |]

    let nonPrimes =
        bases
        |> Array.map (fun b -> set [ (b * 2) .. b .. limit ])
        |> Array.reduce (+)

    candidates - nonPrimes
val generatePrimes : limit:int -> Set<int>

Full name: Script.generatePrimes
val limit : int
val candidates : Set<int>
val set : elements:seq<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.set
val bases : int []
val nonPrimes : Set<int>
module Array

from Microsoft.FSharp.Collections
val map : mapping:('T -> 'U) -> array:'T [] -> 'U []

Full name: Microsoft.FSharp.Collections.Array.map
val b : int
val reduce : reduction:('T -> 'T -> 'T) -> array:'T [] -> 'T

Full name: Microsoft.FSharp.Collections.Array.reduce
Raw view Test code New version

More information

Link:http://fssnip.net/7XR
Posted:4 years ago
Author:galacticdessert
Tags: eratosthenes , euler , math , project euler , set , sets , sieve , sieve of eratosthenes

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.