title: Scala performance - Sieve
body: <p>Right now, I am trying to learn Scala . I've started small, writing some simple algorithms . I've encountered some problems when I wanted to implement the Sieve algorithm from finding all all prime numbers lower than a certain threshold .</p>
  
  <p>My implementation is:</p>
  
  <pre><code>import scala.math
  
  object Sieve {
  
      // Returns all prime numbers until maxNum
      def getPrimes(maxNum : Int) = {
          def sieve(list: List[Int], stop : Int) : List[Int] = {
              list match {
                  case Nil =&gt; Nil
                  case h :: list if h &lt;= stop =&gt; h :: sieve(list.filterNot(_ % h == 0), stop)
                  case _ =&gt; list
              }
          }
          val stop : Int = math.sqrt(maxNum).toInt
          sieve((2 to maxNum).toList, stop)
      }
  
      def main(args: Array[String]) = {
          val ap = printf("%d ", (_:Int)); 
  
          // works
          getPrimes(1000).foreach(ap(_))
  
          // works 
          getPrimes(100000).foreach(ap(_))
  
          // out of memory
          getPrimes(1000000).foreach(ap(_))
  
      }
  }
  </code></pre>
  
  <p>Unfortunately it fails when I want to computer all the prime numbers smaller than 1000000 (1 million) . I am receiving OutOfMemory .</p>
  
  <p>Do you have any idea on how to optimize the code, or how can I implement this algorithm in a more elegant fashion .</p>
  
  <p>PS: I've done something very similar in Haskell, and there I didn't encountered any issues .</p>