Overview of this book

Scala Functional Programming Patterns
Credits
Aknowledgement
www.PacktPub.com
Preface
Free Chapter
Grokking the Functional Way
Singletons, Factories, and Builders
Recursion and Chasing your Own Tail
Lazy Sequences – Being Lazy, Being Good
Taming Multiple Inheritance with Traits
Of Visitors and Chains of Responsibilities
Traversals – Mapping/Filtering/Folding/Reducing
Higher Order Functions
Actors and Message Passing
Index

Sieve of Eratosthenes

Star gazing at night—we sometimes wonder—How many stars are there in the universe? How many galaxies? How many natural numbers are there? All these are really not finite. They are infinite! Prime numbers are also infinite. A brilliant algorithm to find prime numbers was found by Eratosthenes of Cyrene, a Greek mathematician. Named after him, the Sieve of Eratosthenes algorithm can be very nicely expressed as follows:

```scala> def numStream(n: Int): Stream[Int] =
|
Stream.from(n)// 1
numStream: (n: Int)Stream[Int]
scala> def sieve(stream: Stream[Int]): Stream[Int] =
|   stream.head #:: sieve((stream.tail) filter (x => x % stream.head != 0)) // 2
sieve: (stream: Stream[Int])Stream[Int]
scala> val p = sieve(numStream(2))
p: Stream[Int] = Stream(2, ?)
scala> (p take 5) foreach { println(_) }
2
3
5
7
11
```

By dissecting the code, we get the following findings:

1. We have a stream that generates successive numbers, starting off from the argument...