sieve of Eratosthenes
E865104
ancient algorithm
deterministic algorithm
integer algorithm
prime number algorithm
sieving algorithm
The sieve of Eratosthenes is an ancient and efficient algorithm for finding all prime numbers up to a given limit by iteratively eliminating multiples of each prime.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| classical sieve of Eratosthenes | 1 |
Statements (50)
| Predicate | Object |
|---|---|
| instanceOf |
ancient algorithm
ⓘ
deterministic algorithm ⓘ integer algorithm ⓘ prime number algorithm ⓘ sieving algorithm ⓘ |
| advantage | more efficient than trial division for finding many primes up to n ⓘ |
| algorithmType |
incremental elimination algorithm
ⓘ
non-comparative algorithm ⓘ |
| application |
cryptographic key generation precomputation
ⓘ
demonstrating basic algorithm design ⓘ mathematics education ⓘ precomputing primes for number-theoretic algorithms ⓘ |
| approximateDateOfInvention | 3rd century BCE ⓘ |
| comparedTo | more efficient than naive primality testing for ranges of integers ⓘ |
| complexityClass | sub-quadratic in n ⓘ |
| describedIn | works attributed to Eratosthenes ⓘ |
| field |
computational number theory
ⓘ
computer science ⓘ number theory ⓘ |
| input | positive integer n ⓘ |
| limitation |
not suitable for extremely large n without segmentation
ⓘ
requires memory proportional to n ⓘ |
| namedAfter | Eratosthenes of Cyrene NERFINISHED ⓘ |
| optimization |
skip even numbers after handling prime 2
ⓘ
start crossing off multiples from p^2 ⓘ use bit-level storage to reduce memory ⓘ |
| originPeriod | Hellenistic period NERFINISHED ⓘ |
| output | list of all primes less than or equal to n ⓘ |
| property |
does not require division operations after initialization
ⓘ
guarantees all primes up to n are found ⓘ simple to implement ⓘ |
| purpose | finding all prime numbers up to a given integer n ⓘ |
| relatedAlgorithm |
segmented sieve of Eratosthenes
NERFINISHED
ⓘ
sieve of Atkin NERFINISHED ⓘ trial division ⓘ |
| relatedConcept |
composite number
ⓘ
primality testing ⓘ prime number ⓘ sieve theory ⓘ |
| resultCondition | all unmarked numbers are prime ⓘ |
| spaceComplexity | O(n) ⓘ |
| step |
find the next unmarked number greater than the current prime
ⓘ
initialize a list of consecutive integers from 2 to n ⓘ mark all multiples of the current prime as composite ⓘ repeat the process until the square of the current prime exceeds n ⓘ start with the first prime number 2 ⓘ |
| teachesConcept | iterative refinement in algorithms ⓘ |
| timeComplexity | O(n log log n) ⓘ |
| usesDataStructure |
bitset
ⓘ
boolean array ⓘ |
Referenced by (3)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
classical sieve of Eratosthenes