fork download
copy 
  1. open System
  2.  
  3. type SeqDesc<'a> = SeqDesc of 'a * (unit -> SeqDesc<'a>) //' a self referring tuple type
  4.  
  5. let primesMPWSE =
  6.   let whlptrn = [| 2;4;2;4;6;2;6;4;2;4;6;6;2;6;4;2;6;4;6;8;4;2;4;2;
  7.                    4;8;6;4;6;2;4;6;2;6;6;4;2;4;6;2;6;4;2;4;2;10;2;10 |]
  8.   let inline adv i = if i < 47 then i + 1 else 0
  9.   let reinsert oldcmpst mp (prime,pi) =
  10.     let cmpst = oldcmpst + whlptrn.[pi] * prime
  11.     match Map.tryFind cmpst mp with
  12.       | None -> mp |> Map.add cmpst [(prime,adv pi)]
  13.       | Some(facts) -> mp |> Map.add cmpst ((prime,adv pi)::facts)
  14.   let rec mkprimes (n,i) m (SeqDesc((np,npi),nsdf) as psd) q =
  15.     let nxt = n + whlptrn.[i]
  16.     match Map.tryFind n m with
  17.       | None -> if n < q then SeqDesc((n,i),fun() -> mkprimes (nxt,adv i) m psd q)
  18.                 else let (SeqDesc((nhd,x),ntl) as nsd),nxtcmpst = nsdf(),n + whlptrn.[npi] * np
  19.                      mkprimes (nxt,adv i) (Map.add nxtcmpst [(np,adv npi)] m) nsd (nhd * nhd)
  20.       | Some(skips) -> let adjdmap = skips |> List.fold (reinsert n) (m |> Map.remove n)
  21.                        mkprimes (nxt,adv i) adjdmap psd q
  22.   let rec prs = SeqDesc((11,0),fun() -> mkprimes (13,1) Map.empty prs 121 )
  23.   let genseq sd = Seq.unfold (fun (SeqDesc((n,i),tailfunc)) -> Some(n,tailfunc())) sd
  24.   seq { yield 2; yield 3; yield 5; yield 7; yield! mkprimes (11,0) Map.empty prs 121 |> genseq }
  25.  
  26. primesMPWSE |> Seq.nth 100000 |> printfn "%A"
Success #stdin #stdout 1.06s 12720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1299721
https://ideone.com/N5AhCx
Optimized Map based Sieve of Eratosthenese
language:
F# (mono 4.1)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!