LinearSieve.js

const LinearSieve = (n) => {
 /*
 * Calculates prime numbers till a number n
 * Time Complexity: O(n)
 * Explanation: https://cp-algorithms.com/algebra/prime-sieve-linear.html
 * :param n: Number up to which to calculate primes
 * :return: A list containing only primes
 */
 const isnPrime = new Array(n + 1)
 isnPrime[0] = isnPrime[1] = true
 const primes = []
 for (let i = 2; i <= n; i++) {
 if (!isnPrime[i]) primes.push(i)
 for (const p of primes) {
 const k = i * p
 if (k > n) break
 isnPrime[k] = true
 if (i % p === 0) break
 }
 }
 return primes
}

export { LinearSieve }