1unitedpower: Lösung

Beitrag lesen

Ich habe korrekte Einsendungen von @Gunnar Bittersmann und @Rolf B bekommen, ich überlasse es euch sie hier vorzustellen.

Ich habe es mit dem rekursiven Lösungsweg versucht, und erstmal naiv angefangen und das Stackwachstum ignoriert:

// Erzeuge alle natürlichen Zahlen beginnend mit 2
function* nats () {
    let start = 2n;
    while (true) {
        yield start++;
    }
}

// Erzeuge alle Primzahlen
function* primes () {
    yield* filterPrimes(nats())
}

// Siebe alle Primzahlen aus dem übergebenen Iterator
function* filterPrimes(xs) {
    const p = xs.next().value;
    const rest = dropMutliplesOf(p, xs);
    yield p;
    yield* filterPrimes(rest);
}

// Entferne alle Multiplikativen von p aus dem übergebenen Iterator
function* dropMutliplesOf (p, xs) {
    for (const x of xs) {
        if (x % p !== 0n) {
            yield x
        }
    }
}

JavaScript optimiert keine tail-rekursiven Aufrufe in Generatoren, das habe ich auch erst durch die Aufgabe gelernt, deshalb muss der rekursive Aufruf in filterPrimes aufgelöst werden, das hab ich mit einem Trampoline gelöst:


// Erzeuge alle Primzahlen
function* primes () {
    let [p, next] = step(nats2())
    yield p;
    while (true) {
        [p, next] = next()
        yield p
    }
}

// Erzeuge die nächste Primzahl und eine Funktion zum Erzeugen der Übernächsten Primzahl
function step(xs) {
    const p = xs[Symbol.iterator]().next().value;
    const rest = dropMutliplesOf(p, xs);
    return [p, () => step(rest)];
}

In dem Code steckt aber noch eine verteckte Rekursion, nämlich bei der Benutzung von dropMultiplesOf. Die Rekursion habe ich aufgelöst, indem ich den Callstack explizit in einem Parameter kodiert habe.


// Generiere alle Primzahlen
function* primes () {
    let [p, next] = step([], nats2())
    let primes = [p]
    yield p;
    while (true) {
        [p, next] = next(primes)
        primes.push(p)
        yield p
    }
}

// Nimmt eine Liste von zuvor berechneten Primzahlen und einen Iterator der natürlichen Zahlen (beginnend mit 2n) entgegen, liefert die nächste Primzahl und eine Funktion zum berechnen der übernächsten Primzahl.
function step(primes, xs) {
    const p = dropMutliplesOf(primes, xs).next().value;;
    return [p, (primes) => step(primes, xs)];
}

// Filtere alle zahlen aus xs, die keine Vielfachen einer Zahl aus primes sind.
function* dropMutliplesOf (primes, xs) {
    for (const x of xs) {
        if (primes.every(p => x % p !== 0n)) {
            yield x
        }
    }
}

Fazit: Nach dem Trampolining ist der Code fast nicht mehr zu verstehen, schade eigentlich.

Schließlich habe ich noch eine prozedurale Lösung gebaut, zuerst ohne Optimierungen:

// Generiere alle Primzahlen
function* primes () {
    const primes = []
    forX: for (let x = 2n; true; x++) {
        for (let p of primes) {
            if (x % p === 0n) continue forX;
        }
        primes.push(x)
        yield x
    }
}

Und mit Optimierung:

// Generiere alle Primzahlen
function* primes () {
    yield 2n;
    const primes = [2n];
    forX: for (let x = 3n; true; x = x + 2n) {
        for (let p = primes[1], i = 1; (x >= p * p) && (i < primes.length); i++, p = primes[i]) {
            if (x % p === 0n) continue forX;
        }
        primes.push(x)
        yield x
    }
}

Die schnellste Lösung hat @Rolf B eingereicht, obwohl ich glaube, dass meine letzte Variante den selben Algorithmus benutzt, komme ich damit nicht seine Performance heran. Glückwunsch!