JavaScript Primzahlen finden mit dem Sieb des Eratosthenes

Hendoul

Commander
Registriert
Apr. 2008
Beiträge
2.067
Hi :)

Ich habe mal als kleine Übung versucht das Sieb des Eratosthenes anzuwenden für eine Range von Zahlen und darin die Primzahlen möglichst effizient zu finden.

https://stackblitz.com/edit/js-r5jqbm

Javascript:
const log = console.log;

function findAllPrimesWithinRange(from, to) {
  const numbersToSearch = [...Array(to + 1 - from).keys()].map((x) => x + from);
  log('numbers to search - ', numbersToSearch);

  const sqrOfTo = Math.floor(Math.sqrt(to));

  let primesLessThanSqrtOfTo = [...Array(sqrOfTo).keys()].map((x) => x + 1).slice(1);

  primesLessThanSqrtOfTo = sieveIt(primesLessThanSqrtOfTo)
  log('primesLessThanSqrtOfTo - ', primesLessThanSqrtOfTo)

  const result = sieveIt(primesLessThanSqrtOfTo, numbersToSearch);

  log('result - ', result)
}

function sieveIt(initialSieve, numbersToSieve = initialSieve) {
  log('initialSieve - ', initialSieve);
  log('numbersToSieve - ', numbersToSieve);

  for (let i = 0; i < initialSieve.length; i++) {
    for (let j = 0; j < numbersToSieve.length; j++) {
      log(initialSieve[i] + ' ', numbersToSieve[j])
      if (initialSieve[i] === numbersToSieve[j]) {
        continue;
      }

      if (numbersToSieve[j] % initialSieve[i] === 0) {
        const deleted = numbersToSieve.splice(j, 1);
        log('deleted - ', deleted)
        j--;
      }
    }
  }

  return numbersToSieve;
}

findAllPrimesWithinRange(80, 100);


Es funktioniert zwar, aber was ich nicht so schön finde ist, dass ich zweimal sieben muss. Zuerst muss ich ich die Primzahlen finden die kleiner/gleich sind als die Wurzel vom max Wert der Range (im Beispiel 100). Sprich die Primzahlen zwischen 2 und 10. Damit ich diese Nachher auf die eigentliche Range anwenden kann.

Man kann das doch sicher eleganter lösen als ich das gemacht habe? :D
 
Vorab- kein Primzahlexperte :daumen:

Dennoch, ich halte das Sieb für "nicht gut geeignet auf dem Computer". Das ist vielleicht "effizient" für die manuelle Berechnung, keine Ahnung, aber auf dem PC verschwendet man haufenweise Ressourcen damit.

YMMV -- offensichtlich -- aber ich denke, auf dem PC sind andere Methoden effizienter. Auch wenn die vielleicht "manuell" aufwendiger oder umfangreicher sind.
 
Wenn ich mich recht erinnere kannst du doch einfach folgende Schleife verwenden:
  • Nächste Primzahl suchen = nächste noch nicht gelöschte Zahl (anfangen mit der Zwei, Abbruch bei Erreichen der Wurzel(Maximalwert)
  • Alle Vielfachen löschen
Also 2 finden, 4, 6, 8, 10, … löschen
3 finden, 6, 9, 12, … löschen
5 finden, …
7 finden, …
 
Ja wenn man bei 2 beginnt ist es einfacher. Aber was wenn man eben bei z.B. 80 beginnt und bei 100 aufhören möchte. Ok, anstatt modulo zu verwenden könnte ich auch das Array mit true/false befüllen. Wobei ich dann auch mit den 2er, 3er, 5er etc. Schritten streichen müsste, und man nicht sicher sein kann wo beginnen? Vielleicht mit einer Map? Man möchte ja auch vermeiden, dass man unnötigt doppelt/dreifach... streicht. Also wird die 84 ja bereits durch die 2 gestrichen, und muss dann nicht nochmals durch die 7 gestrichen werden. Ach ich krieg Kopfschmerzen :D und probiers mal in einer ruhigen Minute aus.
 
Als erstes auch der Hinweis, grad Nebel im Kopf und könnte Quark schreiben. Aber reicht es nicht bei deinem Beispiel bei der Berechnung der 7 dann nur 7+ rechnest und streichst, die kleinen Faktoren hattest du ja schon?
 
Das Sieb ist halt einfach nicht gedacht für "von-bis"-Bereiche. Niemand sagte, dass das Sieb der ultimative Algorithmus ist...
 

Ähnliche Themen

T
2
Antworten
21
Aufrufe
2.443
1668mib
1
Zurück
Oben