Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita62a46e

Browse files
authored
Resolve duplicate entries for sieve of eratosthenes (#1770)
* remove intarr test* Remove main file oops*FIXES:#1666 , remove references to SieveOfEratosthenesIntArray* Finally fix the requirements, passes vitest* Updated Documentation in README.md*FIXES:#1666 and conform to alg comment standards---------Co-authored-by: SpiderMath <SpiderMath@users.noreply.github.com>
1 parent85a55da commita62a46e

6 files changed

+49
-70
lines changed

‎DIRECTORY.md

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -254,7 +254,6 @@
254254
*[RowEchelon](Maths/RowEchelon.js)
255255
*[ShorsAlgorithm](Maths/ShorsAlgorithm.js)
256256
*[SieveOfEratosthenes](Maths/SieveOfEratosthenes.js)
257-
*[SieveOfEratosthenesIntArray](Maths/SieveOfEratosthenesIntArray.js)
258257
*[Signum](Maths/Signum.js)
259258
*[SimpsonIntegration](Maths/SimpsonIntegration.js)
260259
*[Softmax](Maths/Softmax.js)

‎Maths/SieveOfEratosthenes.js

Lines changed: 22 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -1,25 +1,26 @@
1-
constsieveOfEratosthenes=(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-
constprimes=newArray(n+1)
8-
primes.fill(true)// set all as true initially
9-
primes[0]=primes[1]=false// Handling case for 0 and 1
10-
constsqrtn=Math.ceil(Math.sqrt(n))
11-
for(leti=2;i<=sqrtn;i++){
12-
if(primes[i]){
13-
for(letj=i*i;j<=n;j+=i){
14-
/*
15-
Optimization.
16-
Let j start from i * i, not 2 * i, because smaller multiples of i have been marked false.
1+
/**
2+
*@function sieveOfEratosthenes
3+
*@description Function to get all the prime numbers below a given number using sieve of eratosthenes algorithm
4+
*@param {Number} max The limit below which all the primes are required to be
5+
*@returns {Number[]} An array of all the prime numbers below max
6+
*@see [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
7+
*@example
8+
* sieveOfEratosthenes(1) // ====> []
9+
*@example
10+
* sieveOfEratosthenes(20) // ====> [2, 3, 5, 7, 11, 13, 17, 19]
11+
*
12+
*/
13+
functionsieveOfEratosthenes(max){
14+
constsieve=[]
15+
constprimes=[]
1716

18-
For example, let i = 4.
19-
We do not have to check from 8(4 * 2) to 12(4 * 3)
20-
because they have been already marked false when i=2 and i=3.
21-
*/
22-
primes[j]=false
17+
for(leti=2;i<=max;++i){
18+
if(!sieve[i]){
19+
// If i has not been marked then it is prime
20+
primes.push(i)
21+
for(letj=i<<1;j<=max;j+=i){
22+
// Mark all multiples of i as non-prime
23+
sieve[j]=true
2324
}
2425
}
2526
}

‎Maths/SieveOfEratosthenesIntArray.js

Lines changed: 0 additions & 24 deletions
This file was deleted.
Lines changed: 26 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,29 @@
11
import{sieveOfEratosthenes}from'../SieveOfEratosthenes'
2-
import{PrimeCheck}from'../PrimeCheck'
3-
4-
describe('should return an array of prime booleans',()=>{
5-
it('should have each element in the array as a prime boolean',()=>{
6-
constn=30
7-
constprimes=sieveOfEratosthenes(n)
8-
primes.forEach((primeBool,index)=>{
9-
if(primeBool){
10-
expect(PrimeCheck(index)).toBeTruthy()
11-
}
12-
})
2+
3+
describe('sieveOfEratosthenes',()=>{
4+
test('returns an empty array for max < 2',()=>{
5+
expect(sieveOfEratosthenes(1)).toEqual([])
6+
})
7+
8+
test('returns [2] for max = 2',()=>{
9+
expect(sieveOfEratosthenes(2)).toEqual([2])
10+
})
11+
12+
test('returns [2, 3] for max = 3',()=>{
13+
expect(sieveOfEratosthenes(3)).toEqual([2,3])
14+
})
15+
16+
test('returns [2, 3, 5, 7] for max = 10',()=>{
17+
expect(sieveOfEratosthenes(10)).toEqual([2,3,5,7])
18+
})
19+
20+
test('returns [2, 3, 5, 7, 11, 13, 17, 19] for max = 20',()=>{
21+
expect(sieveOfEratosthenes(20)).toEqual([2,3,5,7,11,13,17,19])
22+
})
23+
24+
test('returns [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] for max = 30',()=>{
25+
expect(sieveOfEratosthenes(30)).toEqual([
26+
2,3,5,7,11,13,17,19,23,29
27+
])
1328
})
1429
})

‎Maths/test/SieveOfEratosthenesIntArray.test.js

Lines changed: 0 additions & 12 deletions
This file was deleted.

‎Project-Euler/Problem035.js

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*
1010
*@author ddaniel27
1111
*/
12-
import{sieveOfEratosthenes}from'../Maths/SieveOfEratosthenesIntArray'
12+
import{sieveOfEratosthenes}from'../Maths/SieveOfEratosthenes'
1313

1414
functionproblem35(n){
1515
if(n<2){

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp