An incremental primal sieve (Q1080878)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An incremental primal sieve |
scientific article |
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
