Last active
November 15, 2017 09:44
-
-
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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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