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

Commit943f834

Browse files
jpvg10trekhleb
authored andcommitted
Adding Sieve of Eratosthenes (trekhleb#46)
* Adding Sieve of Eratosthenes* Typo
1 parent870c3ba commit943f834

File tree

3 files changed

+69
-0
lines changed

3 files changed

+69
-0
lines changed
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
#Sieve of Eratosthenes
2+
3+
The Sieve of Eratosthenes is an algorithm for finding all prime numbers up to some limit`n`.
4+
5+
It is attributed to Eratosthenes of Cyrene, an ancient Greek mathematician.
6+
7+
##How it works
8+
9+
1. Create a boolean array of`n+1` positions (to represent the numbers`0` through`n`)
10+
2. Set positions`0` and`1` to`false`, and the rest to`true`
11+
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)
13+
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
14+
15+
When the algorithm terminates, the numbers remaining`true` in the array are all the primes below`n`.
16+
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+
19+
##Example
20+
21+
![Sieve](https://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif)
22+
23+
##Complexity
24+
25+
The algorithm has a complexity of`O(n log(log n))`.
26+
27+
##References
28+
29+
[Wikipedia](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
importsieveOfEratosthenesfrom'../sieveOfEratosthenes';
2+
3+
describe('factorial',()=>{
4+
it('should find all primes less than or equal to n',()=>{
5+
expect(sieveOfEratosthenes(5)).toEqual([2,3,5]);
6+
expect(sieveOfEratosthenes(10)).toEqual([2,3,5,7]);
7+
expect(sieveOfEratosthenes(100)).toEqual([
8+
2,3,5,7,11,13,17,19,23,29,31,37,41,
9+
43,47,53,59,61,67,71,73,79,83,89,97,
10+
]);
11+
});
12+
});
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
/**
2+
*@param {number} n
3+
*@return {number[]}
4+
*/
5+
exportdefaultfunctionsieveOfEratosthenes(n){
6+
constisPrime=newArray(n+1).fill(true);
7+
isPrime[0]=false;
8+
isPrime[1]=false;
9+
constprimes=[];
10+
11+
for(leti=2;i<=n;i+=1){
12+
if(isPrime[i]===true){
13+
primes.push(i);
14+
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;
19+
20+
while(j<=n){
21+
isPrime[j]=false;
22+
j+=i;
23+
}
24+
}
25+
}
26+
27+
returnprimes;
28+
}

0 commit comments

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