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
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?
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?