An incremental primal sieve (Q1080878): Difference between revisions

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.