| 7 | * @see https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes |
| 8 | */ |
| 9 | export function sieveOfEratosthenes(limit: number): number[] { |
| 10 | if (!Number.isInteger(limit) || limit <= 1) { |
| 11 | throw new Error('limit should be an integer greater than 1') |
| 12 | } |
| 13 | |
| 14 | const maybePrime: boolean[] = new Array(limit + 1).fill(true) |
| 15 | for (let i = 2; i * i <= limit; i++) { |
| 16 | if (!maybePrime[i]) continue |
| 17 | for (let j = i * i; j <= limit; j += i) { |
| 18 | maybePrime[j] = false |
| 19 | } |
| 20 | } |
| 21 | |
| 22 | const primes: number[] = [] |
| 23 | for (let i = 2; i < maybePrime.length; i++) { |
| 24 | if (maybePrime[i]) { |
| 25 | primes.push(i) |
| 26 | } |
| 27 | } |
| 28 | |
| 29 | return primes |
| 30 | } |
| 31 | |
| 32 | /** |
| 33 | * Generator that yields primes. |