Find prime numbers high order function

Question

I want to find prime numbers using collection functions. I generate numbers from 1 to 10000 then I decide to take first number starting from 2, let's name it X and replace it with -1 or delete where X%Y === 0 Y is any numbers after X.

Code:

val list = (2 to 10000)
println(list.map(x => list.filter(y => y % x == 0)))

but this code wrong, ugly, have so bad performance how can I do it truly functional way?

no, I think it can be helpful for other people because of the search keywords — tenshi, Jan 26 '14 at 15:51

score 1 · Accepted Answer · answered Jan 26 '14 at 17:37

1

I solved the same task with this:

import scala.annotation.tailrec

def primesBelow(x: Int): List[Int] = {
  @tailrec
  def iter(primes: List[Int], xs: List[Int]): List[Int] = xs match {
    case Nil => primes
    case x :: xs => iter(x :: primes, xs.filter(_ % x != 0))
  }
  iter(Nil, (2 until x).toList).reverse
}

answered Jan 26 '14 at 17:37

pyanzin

120
3
10

1

it is much *much* faster if `iter` stops at the sqrt: `def primesBelow(n): ... xs match { ... case x :: rest => IF (x*x > n) THEN primes.reverse.append(xs) ELSE iter(...) } ...`. :) – Will Ness Jan 26 '14 at 18:53

Find prime numbers high order function

1 Answers1