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

Commit91d4714

Browse files
committed
Code styling fixes for Sieve of Eratosthenes.
1 parent943f834 commit91d4714

File tree

4 files changed

+31
-19
lines changed

4 files changed

+31
-19
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -49,6 +49,7 @@ a set of rules that precisely define a sequence of operations.
4949
*[Euclidean Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/euclidean-algorithm) - calculate the Greatest Common Divisor (GCD)
5050
*[Least Common Multiple](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/least-common-multiple) (LCM)
5151
*[Integer Partition](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/integer-partition)
52+
*[Sieve of Eratosthenes](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/sieve-of-eratosthenes) - finding all prime numbers up to any given limit
5253
***Sets**
5354
*[Cartesian Product](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/cartesian-product) - product of multiple sets
5455
*[Power Set](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/power-set) - all subsets of a set

‎src/algorithms/math/sieve-of-eratosthenes/README.md

Lines changed: 8 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -6,15 +6,18 @@ It is attributed to Eratosthenes of Cyrene, an ancient Greek mathematician.
66

77
##How it works
88

9-
1. Create a boolean array of`n+1` positions (to represent the numbers`0` through`n`)
9+
1. Create a boolean array of`n +1` positions (to represent the numbers`0` through`n`)
1010
2. Set positions`0` and`1` to`false`, and the rest to`true`
1111
3. Start at position`p = 2` (the first prime number)
12-
4. Mark as`false` all the multiples of`p` (that is, positions`2*p`,`3*p`,`4*p`... until you reach the end of the array)
12+
4. Mark as`false` all the multiples of`p` (that is, positions`2 *p`,`3 *p`,`4 *p`... until you reach the end of the array)
1313
5. Find the first position greater than`p` that is`true` in the array. If there is no such position, stop. Otherwise, let`p` equal this new number (which is the next prime), and repeat from step 4
1414

15-
When the algorithm terminates, the numbers remaining`true` in the array are all the primes below`n`.
15+
When the algorithm terminates, the numbers remaining`true` in the array are all
16+
the primes below`n`.
1617

17-
An improvement of this algorithm is, in step 4, start marking multiples of`p` from`p*p`, and not from`2*p`. The reason why this works is because, at that point, smaller multiples of`p` will have already been marked`false`.
18+
An improvement of this algorithm is, in step 4, start marking multiples
19+
of`p` from`p * p`, and not from`2 * p`. The reason why this works is because,
20+
at that point, smaller multiples of`p` will have already been marked`false`.
1821

1922
##Example
2023

@@ -26,4 +29,4 @@ The algorithm has a complexity of `O(n log(log n))`.
2629

2730
##References
2831

29-
[Wikipedia](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
32+
-[Wikipedia](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)

‎src/algorithms/math/sieve-of-eratosthenes/__test__/sieveOfEratosthenes.test.js

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
importsieveOfEratosthenesfrom'../sieveOfEratosthenes';
22

3-
describe('factorial',()=>{
3+
describe('sieveOfEratosthenes',()=>{
44
it('should find all primes less than or equal to n',()=>{
55
expect(sieveOfEratosthenes(5)).toEqual([2,3,5]);
66
expect(sieveOfEratosthenes(10)).toEqual([2,3,5,7]);

‎src/algorithms/math/sieve-of-eratosthenes/sieveOfEratosthenes.js

Lines changed: 21 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,25 +1,33 @@
11
/**
2-
*@param {number}n
2+
*@param {number}maxNumber
33
*@return {number[]}
44
*/
5-
exportdefaultfunctionsieveOfEratosthenes(n){
6-
constisPrime=newArray(n+1).fill(true);
5+
exportdefaultfunctionsieveOfEratosthenes(maxNumber){
6+
constisPrime=newArray(maxNumber+1).fill(true);
77
isPrime[0]=false;
88
isPrime[1]=false;
9+
910
constprimes=[];
1011

11-
for(leti=2;i<=n;i+=1){
12-
if(isPrime[i]===true){
13-
primes.push(i);
12+
for(letnumber=2;number<=maxNumber;number+=1){
13+
if(isPrime[number]===true){
14+
primes.push(number);
1415

15-
// Warning: When working with really big numbers, the following line may cause overflow
16-
// In that case, it can be changed to:
17-
// let j = 2 * i;
18-
letj=i*i;
16+
/*
17+
* Optimisation.
18+
* Start marking multiples of `p` from `p * p`, and not from `2 * p`.
19+
* The reason why this works is because, at that point, smaller multiples
20+
* of `p` will have already been marked `false`.
21+
*
22+
* Warning: When working with really big numbers, the following line may cause overflow
23+
* In that case, it can be changed to:
24+
* let nextNumber = 2 * number;
25+
*/
26+
letnextNumber=number*number;
1927

20-
while(j<=n){
21-
isPrime[j]=false;
22-
j+=i;
28+
while(nextNumber<=maxNumber){
29+
isPrime[nextNumber]=false;
30+
nextNumber+=number;
2331
}
2432
}
2533
}

0 commit comments

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