mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-04 07:29:47 +08:00
a62a46e732
* remove intarr test * Remove main file oops * FIXES: #1666 , remove references to SieveOfEratosthenesIntArray * Finally fix the requirements, passes vitest * Updated Documentation in README.md * FIXES: #1666 and conform to alg comment standards --------- Co-authored-by: SpiderMath <SpiderMath@users.noreply.github.com>
31 lines
906 B
JavaScript
31 lines
906 B
JavaScript
/**
|
|
* @function sieveOfEratosthenes
|
|
* @description Function to get all the prime numbers below a given number using sieve of eratosthenes algorithm
|
|
* @param {Number} max The limit below which all the primes are required to be
|
|
* @returns {Number[]} An array of all the prime numbers below max
|
|
* @see [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
|
|
* @example
|
|
* sieveOfEratosthenes(1) // ====> []
|
|
* @example
|
|
* sieveOfEratosthenes(20) // ====> [2, 3, 5, 7, 11, 13, 17, 19]
|
|
*
|
|
*/
|
|
function sieveOfEratosthenes(max) {
|
|
const sieve = []
|
|
const primes = []
|
|
|
|
for (let i = 2; i <= max; ++i) {
|
|
if (!sieve[i]) {
|
|
// If i has not been marked then it is prime
|
|
primes.push(i)
|
|
for (let j = i << 1; j <= max; j += i) {
|
|
// Mark all multiples of i as non-prime
|
|
sieve[j] = true
|
|
}
|
|
}
|
|
}
|
|
return primes
|
|
}
|
|
|
|
export { sieveOfEratosthenes }
|