FilesExpand file tree

master

/

LinearSieve.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

24 lines (23 loc) · 629 Bytes

master

/

LinearSieve.js

Copy path

Top

File metadata and controls

• Code
• Blame

24 lines (23 loc) · 629 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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 }