Lösung
bearbeitet von 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* → 2*n* → 3*n* → 4*n* …?
* verdoppeln: *n* → 2*n* → 4*n* → 8*n* …?
* oder gar um den Faktor der nächsten Primzahl: *n* → 2*n* → 6*n* → 30*n* …?
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](https://bittersmann.de/test/prime-iterator/eratosthenesIteratorFunction.js) ∙ [Testseite](https://bittersmann.de/test/prime-iterator/)
Da bislang kein anständiger Browser `BigInt` unterstützt, hab ich das zunächst mit normalen Zahlen implementiert. Und dann nochmal: [eratosthenesIteratorFunction-bigint.js](https://bittersmann.de/test/prime-iterator/eratosthenesIteratorFunction-bigint.js).
Welches Script geladen wird, wird per *feature detection*{:@en} ermittelt:
~~~HTML
<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()`{:.language-js} an der Stelle OK oder gibt’s da was Besseres?
LLAP 🖖
--
*„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“* —Kurt Weidemann
Lösung
bearbeitet von 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* → 2*n* → 3*n* → 4*n* …?
* verdoppeln: *n* → 2*n* → 4*n* → 8*n* …?
* oder gar um den Faktor der nächsten Primzahl: *n* → 2*n* → 6*n* → 30*n* …?
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](https://bittersmann.de/test/prime-iterator/eratosthenesIteratorFunction.js) ∙ [Testseite](https://bittersmann.de/test/prime-iterator/)
Da bislang kein anständiger Browser `BigInt` unterstützt, hab ich das zunächst mit normlen Zahlen implementiert. Und dann nochmal: [eratosthenesIteratorFunction-bigint.js](https://bittersmann.de/test/prime-iterator/eratosthenesIteratorFunction-bigint.js).
Welches Script geladen wird, wird per *feature detection*{:@en} ermittelt:
~~~HTML
<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()`{:.language-js} an der Stelle OK oder gibt’s da was Besseres?
LLAP 🖖
--
*„Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“* —Kurt Weidemann