◐ Shell
reader mode source ↗
Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
File filter
Conversations
Jump to
Diff view
Apply and reload
Show whitespace
Diff view
Apply and reload
1 change: 0 additions & 1 deletion DIRECTORY.md
Original file line number Diff line number Diff line change
Expand Up @@ -254,7 +254,6 @@
* [RowEchelon](Maths/RowEchelon.js)
* [ShorsAlgorithm](Maths/ShorsAlgorithm.js)
* [SieveOfEratosthenes](Maths/SieveOfEratosthenes.js)
* [SieveOfEratosthenesIntArray](Maths/SieveOfEratosthenesIntArray.js)
* [Signum](Maths/Signum.js)
* [SimpsonIntegration](Maths/SimpsonIntegration.js)
* [Softmax](Maths/Softmax.js)
Expand Down
43 changes: 22 additions & 21 deletions Maths/SieveOfEratosthenes.js
Original file line number Diff line number Diff line change
@@ -1,25 +1,26 @@
const sieveOfEratosthenes = (n) => {
/*
* Calculates prime numbers till a number n
* :param n: Number up to which to calculate primes
* :return: A boolean list containing only primes
*/
const primes = new Array(n + 1)
primes.fill(true) // set all as true initially
primes[0] = primes[1] = false // Handling case for 0 and 1
const sqrtn = Math.ceil(Math.sqrt(n))
for (let i = 2; i <= sqrtn; i++) {
if (primes[i]) {
for (let j = i * i; j <= n; j += i) {
/*
Optimization.
Let j start from i * i, not 2 * i, because smaller multiples of i have been marked false.

For example, let i = 4.
We do not have to check from 8(4 * 2) to 12(4 * 3)
because they have been already marked false when i=2 and i=3.
*/
primes[j] = false
}
}
}
Expand Down
24 changes: 0 additions & 24 deletions Maths/SieveOfEratosthenesIntArray.js
37 changes: 26 additions & 11 deletions Maths/test/SieveOfEratosthenes.test.js
Original file line number Diff line number Diff line change
@@ -1,14 +1,29 @@
import { sieveOfEratosthenes } from '../SieveOfEratosthenes'
import { PrimeCheck } from '../PrimeCheck'

describe('should return an array of prime booleans', () => {
it('should have each element in the array as a prime boolean', () => {
const n = 30
const primes = sieveOfEratosthenes(n)
primes.forEach((primeBool, index) => {
if (primeBool) {
expect(PrimeCheck(index)).toBeTruthy()
}
})
})
})
12 changes: 0 additions & 12 deletions Maths/test/SieveOfEratosthenesIntArray.test.js
2 changes: 1 addition & 1 deletion Project-Euler/Problem035.js
Original file line number Diff line number Diff line change
@@ -9,7 +9,7 @@
*
* @author ddaniel27
*/
import { sieveOfEratosthenes } from '../Maths/SieveOfEratosthenesIntArray'

function problem35(n) {
if (n < 2) {
Expand Down
Toggle all file notes Toggle all file annotations