4 people like it.

# Sieve of Atkin

Modern and efficient algorithm to generate prime numbers up to certain number Uses Parallel Async to run computations in parallel

 ``` 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: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: ``` ``````// Create sieve let initSieve topCandidate = let result = Array.zeroCreate (topCandidate + 1) Array.set result 2 true Array.set result 3 true Array.set result 5 true result // Remove squares of primes let removeSquares sieve topCandidate = let squares = seq { 7 .. topCandidate} |> Seq.filter (fun n -> Array.get sieve n) |> Seq.map (fun n -> n * n) |> Seq.takeWhile (fun n -> n <= topCandidate) for n2 in squares do n2 |> Seq.unfold (fun state -> Some(state, state + n2)) |> Seq.takeWhile (fun x -> x <= topCandidate) |> Seq.iter (fun x -> Array.set sieve x false) sieve // Pick the primes and return as an Array let pickPrimes sieve = sieve |> Array.mapi (fun i t -> if t then Some i else None) |> Array.choose (fun t -> t) // Flip solutions of the first equation let doFirst sieve topCandidate = let set1 = Set.ofList [1; 13; 17; 29; 37; 41; 49; 53] let mutable x = 1 let mutable y = 1 let mutable go = true let mutable x2 = 4 * x * x while go do let n = x2 + y*y if n <= topCandidate then if Set.contains (n % 60) set1 then Array.get sieve n |> not |> Array.set sieve n y <- y + 2 else y <- 1 x <- x + 1 x2 <- 4 * x * x if topCandidate < x2 + 1 then go <- false // Flip solutions of the second equation let doSecond sieve topCandidate = let set2 = Set.ofList [7; 19; 31; 43] let mutable x = 1 let mutable y = 2 let mutable go = true let mutable x2 = 3 * x * x while go do let n = x2 + y*y if n <= topCandidate then if Set.contains (n % 60) set2 then Array.get sieve n |> not |> Array.set sieve n y <- y + 2 else y <- 2 x <- x + 2 x2 <- 3 * x * x if topCandidate < x2 + 4 then go <- false // Flip solutions of the third equation let doThird sieve topCandidate = let set3 = Set.ofList [11; 23; 47; 59] let mutable x = 2 let mutable y = x - 1 let mutable go = true let mutable x2 = 3 * x * x while go do let n = x2 - y*y if n <= topCandidate && 0 < y then if Set.contains (n % 60) set3 then Array.get sieve n |> not |> Array.set sieve n y <- y - 2 else x <- x + 1 y <- x - 1 x2 <- 3 * x * x if topCandidate < x2 - y*y then go <- false // Sieve of Atkin let ListAtkin (topCandidate : int) = let sieve = initSieve topCandidate [async { doFirst sieve topCandidate } async { doSecond sieve topCandidate } async { doThird sieve topCandidate }] |> Async.Parallel |> Async.RunSynchronously |> ignore removeSquares sieve topCandidate |> pickPrimes ``````
val initSieve : topCandidate:int -> bool []

Full name: Script.initSieve
val topCandidate : int
val result : bool []
module Array

from Microsoft.FSharp.Collections
val zeroCreate : count:int -> 'T []

Full name: Microsoft.FSharp.Collections.Array.zeroCreate
type bool = System.Boolean

Full name: Microsoft.FSharp.Core.bool
val set : array:'T [] -> index:int -> value:'T -> unit

Full name: Microsoft.FSharp.Collections.Array.set
val removeSquares : sieve:bool [] -> topCandidate:int -> bool []

Full name: Script.removeSquares
val sieve : bool []
val squares : seq<int>
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

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

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

Full name: Microsoft.FSharp.Collections.seq<_>
module Seq

from Microsoft.FSharp.Collections
val filter : predicate:('T -> bool) -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.filter
val n : int
val get : array:'T [] -> index:int -> 'T

Full name: Microsoft.FSharp.Collections.Array.get
val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

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

Full name: Microsoft.FSharp.Collections.Seq.takeWhile
val n2 : int
val unfold : generator:('State -> ('T * 'State) option) -> state:'State -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.unfold
val state : int
union case Option.Some: Value: 'T -> Option<'T>
val x : int
val iter : action:('T -> unit) -> source:seq<'T> -> unit

Full name: Microsoft.FSharp.Collections.Seq.iter
val pickPrimes : sieve:bool [] -> int []

Full name: Script.pickPrimes
val mapi : mapping:(int -> 'T -> 'U) -> array:'T [] -> 'U []

Full name: Microsoft.FSharp.Collections.Array.mapi
val i : int
val t : bool
union case Option.None: Option<'T>
val choose : chooser:('T -> 'U option) -> array:'T [] -> 'U []

Full name: Microsoft.FSharp.Collections.Array.choose
val t : int option
val doFirst : sieve:bool [] -> topCandidate:int -> unit

Full name: Script.doFirst
val set1 : Set<int>
Multiple items
module Set

from Microsoft.FSharp.Collections

--------------------
type Set<'T (requires comparison)> =
interface IComparable
interface IEnumerable
interface IEnumerable<'T>
interface ICollection<'T>
new : elements:seq<'T> -> Set<'T>
member Add : value:'T -> Set<'T>
member Contains : value:'T -> bool
override Equals : obj -> bool
member IsProperSubsetOf : otherSet:Set<'T> -> bool
member IsProperSupersetOf : otherSet:Set<'T> -> bool
...

Full name: Microsoft.FSharp.Collections.Set<_>

--------------------
new : elements:seq<'T> -> Set<'T>
val ofList : elements:'T list -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.ofList
val mutable x : int
val mutable y : int
val mutable go : bool
val mutable x2 : int
val contains : element:'T -> set:Set<'T> -> bool (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.contains
val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not
val doSecond : sieve:bool [] -> topCandidate:int -> unit

Full name: Script.doSecond
val set2 : Set<int>
val doThird : sieve:bool [] -> topCandidate:int -> unit

Full name: Script.doThird
val set3 : Set<int>
val ListAtkin : topCandidate:int -> int []

Full name: Script.ListAtkin
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 async : AsyncBuilder

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.async
Multiple items
type Async
static member AsBeginEnd : computation:('Arg -> Async<'T>) -> ('Arg * AsyncCallback * obj -> IAsyncResult) * (IAsyncResult -> 'T) * (IAsyncResult -> unit)
static member AwaitEvent : event:IEvent<'Del,'T> * ?cancelAction:(unit -> unit) -> Async<'T> (requires delegate and 'Del :> Delegate)
static member AwaitIAsyncResult : iar:IAsyncResult * ?millisecondsTimeout:int -> Async<bool>
static member AwaitWaitHandle : waitHandle:WaitHandle * ?millisecondsTimeout:int -> Async<bool>
static member CancelDefaultToken : unit -> unit
static member Catch : computation:Async<'T> -> Async<Choice<'T,exn>>
static member FromBeginEnd : beginAction:(AsyncCallback * obj -> IAsyncResult) * endAction:(IAsyncResult -> 'T) * ?cancelAction:(unit -> unit) -> Async<'T>
static member FromBeginEnd : arg:'Arg1 * beginAction:('Arg1 * AsyncCallback * obj -> IAsyncResult) * endAction:(IAsyncResult -> 'T) * ?cancelAction:(unit -> unit) -> Async<'T>
static member FromBeginEnd : arg1:'Arg1 * arg2:'Arg2 * beginAction:('Arg1 * 'Arg2 * AsyncCallback * obj -> IAsyncResult) * endAction:(IAsyncResult -> 'T) * ?cancelAction:(unit -> unit) -> Async<'T>
static member FromBeginEnd : arg1:'Arg1 * arg2:'Arg2 * arg3:'Arg3 * beginAction:('Arg1 * 'Arg2 * 'Arg3 * AsyncCallback * obj -> IAsyncResult) * endAction:(IAsyncResult -> 'T) * ?cancelAction:(unit -> unit) -> Async<'T>
static member FromContinuations : callback:(('T -> unit) * (exn -> unit) * (OperationCanceledException -> unit) -> unit) -> Async<'T>
static member Ignore : computation:Async<'T> -> Async<unit>
static member OnCancel : interruption:(unit -> unit) -> Async<IDisposable>
static member Parallel : computations:seq<Async<'T>> -> Async<'T []>
static member RunSynchronously : computation:Async<'T> * ?timeout:int * ?cancellationToken:CancellationToken -> 'T
static member Sleep : millisecondsDueTime:int -> Async<unit>
static member Start : computation:Async<unit> * ?cancellationToken:CancellationToken -> unit
static member StartChild : computation:Async<'T> * ?millisecondsTimeout:int -> Async<Async<'T>>
static member StartImmediate : computation:Async<unit> * ?cancellationToken:CancellationToken -> unit
static member StartWithContinuations : computation:Async<'T> * continuation:('T -> unit) * exceptionContinuation:(exn -> unit) * cancellationContinuation:(OperationCanceledException -> unit) * ?cancellationToken:CancellationToken -> unit
static member SwitchToContext : syncContext:SynchronizationContext -> Async<unit>
static member SwitchToNewThread : unit -> Async<unit>
static member SwitchToThreadPool : unit -> Async<unit>
static member TryCancelled : computation:Async<'T> * compensation:(OperationCanceledException -> unit) -> Async<'T>
static member CancellationToken : Async<CancellationToken>
static member DefaultCancellationToken : CancellationToken

Full name: Microsoft.FSharp.Control.Async

--------------------
type Async<'T>

Full name: Microsoft.FSharp.Control.Async<_>
static member Async.Parallel : computations:seq<Async<'T>> -> Async<'T []>
static member Async.RunSynchronously : computation:Async<'T> * ?timeout:int * ?cancellationToken:System.Threading.CancellationToken -> 'T
val ignore : value:'T -> unit

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