A sublinear additive sieve for finding prime number

DOI10.1145/358527.358540zbMath0454.68084OpenAlexW2040572975WikidataQ129573780 ScholiaQ129573780MaRDI QIDQ3902523

Paul A. Pritchard

Publication date: 1981

Published in: Communications of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/358527.358540

zbMATH Keywords

algorithmscorrectness proofs

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Primes (11A41) Primality (11Y11)

Related Items (11)

An incremental primal sieve ⋮ Two compact incremental prime sieves ⋮ Factoring polynomials with rational coefficients ⋮ On Faster Integer Calculations Using Non-arithmetic Primitives ⋮ A space-efficient fast prime number sieve ⋮ ON THE COMPLEXITY OF COMPUTING PRIME TABLES ON THE TURING MACHINE ⋮ Iterated Absolute Values of Differences of Consecutive Primes ⋮ Approximating the number of integers free of large prime factors ⋮ A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits ⋮ An estimate for the number of integers without large prime factors ⋮ Prime sieves using binary quadratic forms

This page was built for publication: A sublinear additive sieve for finding prime number