Lösung

[Gunnar Bittersmann]

@@Gunnar Bittersmann

An die lächerliche Geschwindigkeit – äh wahnsinnige Geschwindigkeit – äh enorme Schwierigkeit hab ich mich später gewagt; dazu später mehr.

Beim Itarator habe ich erst gerätselt, wie ich das n Elemente große Array, in welchem gesiebt wird, denn schrittweise erweitern sollte, wenn man an dessen Ende ankommt:

• jeweils um die nächsten n Elemente: n → 2n → 3n → 4n …?
• verdoppeln: n → 2n → 4n → 8n …?
• oder gar um den Faktor der nächsten Primzahl: n → 2n → 6n → 30n …?

Gar nicht. Ich nutze eine andere Datenstruktur: ein zweidimensionales Array: in primes[i][0] stehen die Primzahlen; in primes[i][1] jeweils Vielfache davon. In primes[0][0] steht dann die 3; in primes[0][1] wird durchgezählt: 6, 9, 12, …

Wie schon zuvor, wird die 2 extra ausgeheben und nur noch ungerade Zahlen betrachet: current zählt munter durch: 3, 5, 7, 9, …

Die Vielfachen der vorher schon ermittelten Primzahlen werden solange hochgezählt, bis eine Zahl ≥ current rauskommt. Bei Gleichheit ist current ein Vielfaches, also keine Primzahl. → Nächstes current untersuchen.

Bei Ungleichheit: nächste Primzahl aus dem Array prüfen, ob current ein Vielfaches davon ist. Bei √current kann man aufhören. Wenn current bis dahin kein Vielfaches einer Primzahl war, ist current selbst eine Primzahl und wird zum Array hinzugefügt.

current | primes 3 | [[3, 6]] 5 | [[3, 6], [5, 10]] 7 | [[3, 6], [5, 10], [7, 14]] 9 | [[3, 9], [5, 10], [7, 14]] 11 | [[3, 12], [5, 10], [7, 14], [11, 22] 13 | [[3, 15], [5, 10], [7, 14], [11, 22], [13, 26]] 15 | [[3, 15], [5, 10], [7, 14], [11, 22], [13, 26]] 17 | [[3, 18], [5, 10], [7, 14], [11, 22], [13, 26], [17, 34]] 19 | [[3, 21], [5, 10], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38]] 21 | [[3, 21], [5, 10], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38]] 23 | [[3, 24], [5, 10], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46]] 25 | [[3, 27], [5, 25], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46]] 27 | [[3, 27], [5, 25], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46]] 29 | [[3, 30], [5, 30], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58]] 31 | [[3, 33], [5, 35], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62]] 33 | [[3, 33], [5, 35], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62]] 35 | [[3, 36], [5, 35], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62]] 37 | [[3, 39], [5, 40], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74]] 39 | [[3, 39], [5, 40], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74]] 41 | [[3, 42], [5, 45], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74], [41, 82]] 43 | [[3, 45], [5, 45], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74], [41, 82], [43, 86]] 45 | [[3, 45], [5, 45], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74], [41, 82], [43, 86]] 47 | [[3, 48], [5, 50], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74], [41, 82], [43, 86], [47, 94]] 49 | [[3, 51], [5, 50], [7, 49], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74], [41, 82], [43, 86], [47, 94]] 51 | [[3, 51], [5, 50], [7, 49], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74], [41, 82], [43, 86], [47, 94]] 53 | [[3, 54], [5, 55], [7, 56], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74], [41, 82], [43, 86], [47, 94], [53, 106]]

☞ Implementierung: eratosthenesIteratorFunction.js ∙ Testseite

function eratosthenesIteratorFunction()
{
	let current = 2, primes = [];
		
	return {
		next: function()
		{
			let isPrime;
			
			if (current === 2)
			{
				current--; /* following `current += 2` results in 3 */
				return { value: 2, done: false };
			}
			
			do
			{
				current += 2;
				
				if (current >= Number.MAX_SAFE_INTEGER)
				{
					return { done: true };
				}
				
				let sqrtCurrent = Math.sqrt(current);
				isPrime = true;
				
				for (let i = 0; isPrime && primes.length && primes[i][0] <= sqrtCurrent; i++)
				{
					while (primes[i][1] < current)
					{
						primes[i][1] += primes[i][0];
					}
				
					isPrime = (primes[i][1] !== current);
				}
			}
			while (!isPrime);
			
			primes.push([current, 2 * current]);						
			return { value: current, done: false };
		}
	};
}

Da bislang kein anständiger Browser BigInt unterstützt, hab ich das zunächst mit normalen Zahlen implementiert. Und dann nochmal: eratosthenesIteratorFunction-bigint.js.

Welches Script geladen wird, wird per feature detection ermittelt:

<script>
	if (typeof BigInt === 'function')
	{
		document.write('<script src="eratosthenesIteratorFunction-bigint.js"><\/script>');
	}
	else
	{
		document.write('<script src="eratosthenesIteratorFunction.js"><\/script>');
	}
</script>

Ist document.write() an der Stelle OK oder gibt’s da was Besseres?

LLAP 🖖