Skip to content

Instantly share code, notes, and snippets.

@paoloiulita
Last active October 14, 2019 13:39
Show Gist options
  • Save paoloiulita/3a03789d6fc6a1c1788f0e4663af1af2 to your computer and use it in GitHub Desktop.
Save paoloiulita/3a03789d6fc6a1c1788f0e4663af1af2 to your computer and use it in GitHub Desktop.
Sieve for finding prime numbers
const arrayOfN = n => Array(n).fill(false).map((n, i) => i + 1);
const isNotDivisor = (a, b) => a === b || a % b !== 0;
const getPrimeNumbers = maxValue => {
const maxIndex = Math.floor(Math.sqrt(maxValue));
let numbersToTest = arrayOfN(maxIndex);
let range = arrayOfN(maxValue);
numbersToTest.splice(0, 1);
numbersToTest.forEach(outerNtt => {
numbersToTest = numbersToTest.filter(innerNtt => isNotDivisor(innerNtt, outerNtt));
});
numbersToTest.forEach(ntt => {
range = range.filter(n => isNotDivisor(n, ntt));
});
return range;
}
const getPrimeNumbersUnoptimized = maxValue => {
const maxIndex = Math.floor(Math.sqrt(maxValue));
let range = arrayOfN(maxValue);
let index = 2;
while (index <= maxIndex) {
range = range.filter(n => isNotDivisor(n, index))
index ++;
}
return range;
}
console.time('Normal');
getPrimeNumbersUnoptimized(10000);
console.timeEnd('Normal');
console.time('Optimized');
getPrimeNumbers(10000);
console.timeEnd('Optimized');
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment