Accepted answer

To list all prime numbers less then specific number you should use Sieve of Eratosthenes. It is much faster then your algorithm.

Your algorithm is so slow becouse it checks every number with all prime numbers less than it until it finds its divisor. So every number will be checked with at least one prime number. But when checked number grows, the list of primes grows and number of possible checks grows.

There will be numbers rejected after many checks. For example number 26 will be rejected after checking 2,3,5,7,11,13.

Additionally every prime number will be accepted after checking all less prime numbers.

Comparing to your algorithm, Sieve of Eratosthenes algorithm will 'touch' every number once marking it as 'prime' or 'not prime'.


As mentioned by @rtruszk, the following code reposted from my answer on the other linked question for a true Sieve of Eratosthenes (SoE) will run much faster than your code for larger ranges:

object SoE {
  def makeSoE_Primes(top: Int): Iterator[Int] = {
    val topndx = (top - 3) / 2
    val nonprms = new scala.collection.mutable.BitSet(topndx + 1)
    def cullp(i: Int) = {
      import scala.annotation.tailrec; val p = i + i + 3
      @tailrec def cull(c: Int): Unit = if (c <= topndx) { nonprms += c; cull(c + p) }
      cull((p * p - 3) >>> 1)
    (0 to (Math.sqrt(top).toInt - 3) >>> 1).filterNot { nonprms }.foreach { cullp }
    Iterator.single(2) ++ (0 to topndx).filterNot { nonprms }.map { i: Int => i + i + 3 }

The above code is mostly of a functional form (using tail recursion or higher order functions as well as immutability other than for the contents of the BitSet array used for fast sieving of composite numbers). It isn't quite as fast as using the Java.util.BitSet, but the resulting code is slightly more elegant.