Escribí una función que genera primos de forma indefinida (wikipedia:Tamiz incremental de Erastothenes) usos corrientes. Devuelve un flujo, pero también combina flujos de múltiplos primos internamente para marcar los próximos compuestos. La definición es concisa, funcional, elegante y fácil de entender, si lo digo yo mismo:

def primes(): Stream[Int] = {
  def merge(a: Stream[Int], b: Stream[Int]): Stream[Int] = {
    def next = a.head min b.head
    Stream.cons(next, merge(if (a.head == next) a.tail else a,
                            if (b.head == next) b.tail else b))
  }
  def test(n: Int, compositeStream: Stream[Int]): Stream[Int] = {
    if (n == compositeStream.head) test(n+1, compositeStream.tail)
    else Stream.cons(n, test(n+1, merge(compositeStream, Stream.from(n*n, n))))
  }
  test(2, Stream.from(4, 2))
}

Pero, obtengo un "java.lang.OutOfMemoryError: Se excedió el límite de sobrecarga del GC" cuando trato de generar el número 1000 primo.

Tengo una solución alternativa que devuelve un iterador sobre primos y utiliza una cola de prioridad de tuplas (múltiples, primos que se usan para generar múltiples) internamente para marcar los próximos compuestos. Funciona bien, pero toma aproximadamente el doble de código, y básicamente tuve que reiniciar desde cero:

import scala.collection.mutable.PriorityQueue
def primes(): Iterator[Int] = {
  // Tuple (composite, prime) is used to generate a primes multiples
  object CompositeGeneratorOrdering extends Ordering[(Long, Int)] {
    def compare(a: (Long, Int), b: (Long, Int)) = b._1 compare a._1
  }
  var n = 2;
  val composites = PriorityQueue(((n*n).toLong, n))(CompositeGeneratorOrdering)
  def advance = {
    while (n == composites.head._1) { // n is composite
      while (n == composites.head._1) { // duplicate composites
        val (multiple, prime) = composites.dequeue
        composites.enqueue((multiple + prime, prime))
      }
      n += 1
    }
    assert(n < composites.head._1)
    val prime = n
    n += 1
    composites.enqueue((prime.toLong * prime.toLong, prime))
    prime
  }
  Iterator.continually(advance)
}

¿Existe una forma sencilla de traducir el código con flujos a código con iteradores? ¿O hay una forma sencilla de hacer que mi primer intento sea más eficiente en la memoria?

Es más fácil pensar en términos de corrientes; Prefiero empezar de esa manera, luego ajustar mi código si es necesario.