The Sieve of Eratosthenes — is a simple, ancient algorithm for finding all prime numbers up to any given limit Implemented using Scala and F#

Sieve.fsx

// The Sieve of Eratosthenes in Code from FP course on Coursera rewritten on F#
let rec sieve(lazyCell: Lazy<Stream<'a>>) = seq {
    match lazyCell.Value with
    | LazyCell(a, lazyTail) ->
        yield a
        yield! sieve(lazyTail) |> Seq.filter (fun n -> n % a > 0)
    | _ -> ()   
}

// Samples from F# interactive
#load @"D:\temp\nat\LazyStreams\LazyStreams.fsx"
open LazyStreams

let primes = sieve(from(2))
primes |> Seq.take(100) |> Seq.toList;;

Sieve.scala

// The Sieve of Eratosthenes in Code from FP course on Coursera
def sieve(s: Stream[Int]): Stream[Int] =
  s.head #:: sieve(s.tail filter (_ % s.head != 0))

// Samples
val primes = sieve(from(2))

(primes take 100).toList

Stream.fsx

// Homemade lazy stream definition from F# and hekoer to convert lazy-list to sequence

type Stream<'a> =
    | LazyCell of 'a * Lazy<Stream<'a>>
    | Empty

let rec from(n) = lazy LazyCell(n, from(n + 1))

let rec toSeq(lazyCell: Lazy<Stream<'a>>) = seq {
    match lazyCell.Value with
    | LazyCell(a, lazyTail)  ->
        yield a
        yield! toSeq(lazyTail)
    | _  -> ()
}

Stream.scala

// Stream defintion from FP couesr on Coursera
// https://d396qusza40orc.cloudfront.net/progfun/lecture_slides%2Fweek7-2.pdf

object Stream {
  def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] {
    def isEmpty = false
    def head = hd
    def tail = tl
  }
  
  val empty = new Stream[Nothing] {
    def isEmpty = true
    def head = throw new NoSuchElementException(”empty.head”)
    def tail = throw new NoSuchElementException(”empty.tail”)
  }
}