Oleksii Trekhleb | Javascript algorithms (Sieve of eratosthenes)
This is a series of books diving deep into the core mechanisms of the JavaScript language.
· 1 phút đọc.
The Sieve of Eratosthenes is an algorithm for finding all prime numbers up to some limit n
.
It is attributed to Eratosthenes of Cyrene, an ancient Greek mathematician.
How it works
- Create a boolean array of
n + 1
positions (to represent the numbers0
throughn
) - Set positions
0
and1
tofalse
, and the rest totrue
- Start at position
p = 2
(the first prime number) - Mark as
false
all the multiples ofp
(that is, positions2 p
,3 p
,4 p
… until you reach the end of the array) - Find the first position greater than
p
that istrue
in the array. If there is no such position, stop. Otherwise, letp
equal this new number (which is the next prime), and repeat from step 4
When the algorithm terminates, the numbers remaining true
in the array are all the primes below n
.
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
.
Example
Complexity
The algorithm has a complexity of O(n log(log n))
.