Commit 02a4cee
authored
merge: optamization,documantation,return Array[bool] => Array[primes only], test case (TheAlgorithms#841)
1 parent 93e57b0 commit 02a4cee
2 files changed
Lines changed: 41 additions & 11 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -1,21 +1,28 @@ | |||
| 1 | + /** | ||
| 2 | + * @function SieveOfEratosthenes | ||
| 3 | + * @description Calculates prime numbers till input number n | ||
| 4 | + * @param {Number} n - The input integer | ||
| 5 | + * @return {Number[]} List of Primes till n. | ||
| 6 | + * @see [Sieve_of_Eratosthenes](https://www.geeksforgeeks.org/sieve-of-eratosthenes/) | ||
| 7 | + */ | ||
| 1 | 8 | function sieveOfEratosthenes (n) { | |
| 2 | - /* | ||
| 3 | - * Calculates prime numbers till a number n | ||
| 4 | - * :param n: Number up to which to calculate primes | ||
| 5 | - * :return: A boolean list containing only primes | ||
| 6 | - */ | ||
| 7 | - const primes = new Array(n + 1) | ||
| 8 | - primes.fill(true) // set all as true initially | ||
| 9 | + if (n <= 1) return [] | ||
| 10 | + const primes = new Array(n + 1).fill(true) // set all as true initially | ||
| 9 | 11 | primes[0] = primes[1] = false // Handling case for 0 and 1 | |
| 10 | - const sqrtn = Math.ceil(Math.sqrt(n)) | ||
| 11 | - for (let i = 2; i <= sqrtn; i++) { | ||
| 12 | + for (let i = 2; i * i <= n; i++) { | ||
| 12 | 13 | if (primes[i]) { | |
| 13 | - for (let j = 2 * i; j <= n; j += i) { | ||
| 14 | + for (let j = i * i; j <= n; j += i) { | ||
| 14 | 15 | primes[j] = false | |
| 15 | 16 | } | |
| 16 | 17 | } | |
| 17 | 18 | } | |
| 18 | - return primes | ||
| 19 | + | ||
| 20 | + return primes.reduce((result, isPrime, index) => { | ||
| 21 | + if (isPrime) { | ||
| 22 | + result.push(index) | ||
| 23 | + } | ||
| 24 | + return result | ||
| 25 | + }, []) | ||
| 19 | 26 | } | |
| 20 | 27 | ||
| 21 | 28 | // Example | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,23 @@ | |||
| 1 | + import { sieveOfEratosthenes } from '../SieveOfEratosthenes' | ||
| 2 | + | ||
| 3 | + describe('SieveOfEratosthenes', () => { | ||
| 4 | + it('Primes till 0', () => { | ||
| 5 | + expect(sieveOfEratosthenes(0)).toEqual([]) | ||
| 6 | + }) | ||
| 7 | + | ||
| 8 | + it('Primes till 1', () => { | ||
| 9 | + expect(sieveOfEratosthenes(1)).toEqual([]) | ||
| 10 | + }) | ||
| 11 | + | ||
| 12 | + it('Primes till 10', () => { | ||
| 13 | + expect(sieveOfEratosthenes(10)).toEqual([2, 3, 5, 7]) | ||
| 14 | + }) | ||
| 15 | + | ||
| 16 | + it('Primes till 23', () => { | ||
| 17 | + expect(sieveOfEratosthenes(23)).toEqual([2, 3, 5, 7, 11, 13, 17, 19, 23]) | ||
| 18 | + }) | ||
| 19 | + | ||
| 20 | + it('Primes till 70', () => { | ||
| 21 | + expect(sieveOfEratosthenes(70)).toEqual([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]) | ||
| 22 | + }) | ||
| 23 | + }) | ||
0 commit comments