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.
All labels observed (2)
| Label | Occurrences |
|---|---|
| sieve of Eratosthenes canonical | 2 |
| classical sieve of Eratosthenes | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T10462064 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: sieve of Eratosthenes Context triple: [Selberg sieve, relatedTo, sieve of Eratosthenes]
-
A.
trial division
The trial division is the part of the Supreme Court of the Australian Capital Territory responsible for hearing and determining cases at first instance, including serious criminal and significant civil matters.
-
B.
Eratosthenes spiral
The Eratosthenes spiral is a geometric visualization of prime numbers generated by the sieve of Eratosthenes, arranging integers in a spiral so that primes form distinctive radial patterns.
-
C.
PRIMOS
PRIMOS is a multi-user, multitasking operating system developed by Prime Computer for its line of minicomputers.
-
D.
Fermat primality test
The Fermat primality test is a probabilistic algorithm that checks whether a number is prime by verifying congruences derived from Fermat's little theorem.
-
E.
Trial Division
The Trial Division is a unit within the New York County District Attorney’s Office responsible for prosecuting criminal cases in court from arraignment through verdict.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: sieve of Eratosthenes Target entity description: 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.
-
A.
trial division
The trial division is the part of the Supreme Court of the Australian Capital Territory responsible for hearing and determining cases at first instance, including serious criminal and significant civil matters.
-
B.
Eratosthenes spiral
The Eratosthenes spiral is a geometric visualization of prime numbers generated by the sieve of Eratosthenes, arranging integers in a spiral so that primes form distinctive radial patterns.
-
C.
PRIMOS
PRIMOS is a multi-user, multitasking operating system developed by Prime Computer for its line of minicomputers.
-
D.
Fermat primality test
The Fermat primality test is a probabilistic algorithm that checks whether a number is prime by verifying congruences derived from Fermat's little theorem.
-
E.
Trial Division
The Trial Division is a unit within the New York County District Attorney’s Office responsible for prosecuting criminal cases in court from arraignment through verdict.
- F. None of above. chosen
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 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: sieve of Eratosthenes Description of subject: 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.
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