An incremental primal sieve (Q1080878)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: An incremental primal sieve |
scientific article; zbMATH DE number 3968662
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An incremental primal sieve |
scientific article; zbMATH DE number 3968662 |
Statements
An incremental primal sieve (English)
0 references
1986
0 references
The author derives a new algorithm for finding all primes between 2 and an incrementally increasing value of \(n\). He discusses how this algorithm can be implemented and shows that it executes with linear arithmetic time and space complexity. The author further shows how previously developed techniques can be used to improve the efficiency of his algorithm to \(O(n/log log n)\) time and space complexity.
0 references
primal sieve
0 references
computational number theory
0 references
algorithm
0 references
space complexity
0 references
