It's quick and dirty and could stand to be improved - my main motivation was to show that it could be done quickly and in a lot fewer lines in Scala than was shown on the presentation slide so it's not the greatest example of code ever written. I've put it up here because blogger's commenting system nukes source code layout.
def primes(n: Int): List[Int] = {
def nomults(s: Int, xs: Seq[Int]): List[Int] = (for (x <- xs if x % s != 0) yield x).toList
def sieve(xs: List[Int]): List[Int] = {
if (xs.isEmpty) xs
else {
val p = xs.first
val nxs = nomults(p, xs drop 1)
p :: sieve(nxs)
}
}
val odds = nomults(2, 2 to n)
2 :: sieve(odds)
}
println( primes(100) )
5 comments:
The scaladoc page for Stream has an implementation using streams, for comparison.
http://www.scala-lang.org/docu/files/api/scala/Stream.html
That example on scaladoc is not actually a Sieve os Eratosthenes. See http://lambda-the-ultimate.org/node/3127.
I agree with Daniel. Besides not implementing the s.o.e. it also performs worse. Oh and runs out of heap space quickly. Have a look at the LtU link. Quite enlightening.
Instead of first/drop, use head/tail. You are using a list, after all, and first, for one, is scheduled for deprecation.
You can test xs.head*xs.head < xs.last as the if condition instead of xs.isEmpty, and that will give you proper Sieve implementation without any trouble. That will cause the list to be traversed at each recursion, which isn't nice. Instead, since nomults is internal, you should add a third parameter, and pass "n" in it at sieve's call to nomult.
What do you think about this stream based implementation?
def primes: Stream[Int] = {
import scala.collection.SortedSet
import scala.collection.immutable.TreeSet
def ps(tuple:(Int,SortedSet[Int])):Stream[(Int, SortedSet[Int])] = {
def np(n:Int):(Int, SortedSet[Int]) =
if (tuple._2.takeWhile(p => p*p <= n).exists(n % _ == 0)) np(n+2)
else (n, TreeSet(n) ++ tuple._2)
Stream.cons(tuple, ps(np(tuple._1 + 2)))
}
Stream.cons((2, TreeSet(2)),ps((3, TreeSet(2,3)))).map(_._1)
}
Post a Comment