Skip to content

Instantly share code, notes, and snippets.

@dinigo
Last active November 15, 2017 09:44
Show Gist options
  • Save dinigo/4e19f2a774b07e7ddb17ffcc935bd612 to your computer and use it in GitHub Desktop.
Save dinigo/4e19f2a774b07e7ddb17ffcc935bd612 to your computer and use it in GitHub Desktop.
Calculate primes till certain number, checking against the already calculated, and only with the ones higher than the sqrt
function primes(max) {
let calculated = [1, 2, 3]; // already calculated primes
let num = 4; // current number being checked
let factors; // factors for the given number
let sqrt; // sqrt for a given number
// if the input is too low to be calculated, just return the default primes
if (max < 5) return calculated;
// otherwhise calculate for each number till you reach max
while (num < max) {
// discard even numbers
if (num % 2 == 1) {
sqrt = Math.sqrt(num); // calculate the sqrt only once per number
const factors = calculated
.filter(el=> el >= sqrt) // discard candidate if lower than the number sqrt
.filter(el=>num % el == 0); // discard candidate if not a factor
// if we found no factor then it's a prime!
if (factors.length == 0) calculated.push(num);
}
num++;
}
return calculated;
}
//const p = primes(10000);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment