Ich habe eine Funktion geschrieben, die Primzahlen auf unbestimmte Zeit erzeugt (Wikipedia:inkrementelles Sieb von Erastothenes) Usings Streams. Es wird ein Stream zurückgegeben, aber auch intern Ströme von Primzahlen zusammengeführt, um kommende Composites zu markieren. Die Definition ist prägnant, funktional, elegant und leicht verständlich, wenn ich das selbst sage:

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))
}

Aber ich bekomme ein "java.lang.OutOfMemoryError: GC-Overhead-Limit überschritten", wenn ich versuche, die 1000ste Primzahl zu generieren.

Ich habe eine alternative Lösung, die einen Iterator über Primzahlen zurückgibt und eine Prioritätswarteschlange von Tupeln (mehrere, Primzahlen, die verwendet werden, um mehrere zu generieren) intern verwendet, um anstehende Verbundwerkstoffe zu markieren. Es funktioniert gut, aber es braucht ungefähr doppelt so viel Code, und ich musste im Grunde von vorne neu starten:

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)
}

Gibt es eine einfache Möglichkeit, den Code mit Streams zu übersetzen, um ihn mit Iteratoren zu codieren? Oder gibt es eine einfache Möglichkeit, meinen ersten Versuch speichereffizienter zu gestalten?

Es ist einfacher, in Strömen zu denken. Ich fange lieber so an und ändere dann meinen Code, falls nötig.