Skip to content

Instantly share code, notes, and snippets.

@tuvo1106
Created December 12, 2018 04:42
Show Gist options
  • Save tuvo1106/d42c74d6bee0b48e96ea4baff743d0f0 to your computer and use it in GitHub Desktop.
Save tuvo1106/d42c74d6bee0b48e96ea4baff743d0f0 to your computer and use it in GitHub Desktop.
eratosthenes algorithm for prime numbers
const eratosthenes = n => {
const output = []
const upperLimit = Math.sqrt(n)
// new array with n values of true i.e. [true, true, true...]
const array = Array(n).fill(true)
// loop from 2 to square root of n
for (let i = 2; i <= upperLimit; i++) {
// if i has been marked false, skip
if (array[i]) {
console.log(`i = ${i}`)
// for inner loop, mark all multiples of i as false
for (let j = i * i; j < n; j += i) {
console.log(`${j} is not a prime`)
array[j] = false;
}
}
}
// loop through array and push all true values into output
array.forEach((e, i) => {
if (e) output.push(i)
})
// slice 0 and 1 because those are not prime
return output.slice(2)
};
console.log(eratosthenes(10)) // [ 2, 3, 5, 7 ]
console.log(eratosthenes(50)) // [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 ]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment