Prime sieves using binary quadratic forms

DOI10.1090/S0025-5718-03-01501-1zbMath1049.11137OpenAlexW2090725688WikidataQ30040407 ScholiaQ30040407MaRDI QIDQ4452178

A. O. L. Atkin, Daniel J. Bernstein

Publication date: 12 February 2004

Published in: Mathematics of Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0025-5718-03-01501-1

zbMATH Keywords

binary quadratic formsprimalityprime sieves

Mathematics Subject Classification ID

Sums of squares and representations by other particular quadratic forms (11E25) Primes (11A41) Primality (11Y11)

Related Items

Two compact incremental prime sieves ⋮ Pattern matching with wildcards using words of shorter length ⋮ \textsc{Rings}: an efficient Java/Scala library for polynomial rings ⋮ ON THE COMPLEXITY OF COMPUTING PRIME TABLES ON THE TURING MACHINE ⋮ Empirical verification of the even Goldbach conjecture and computation of prime gaps up to 4⋅10¹⁸ ⋮ IDENTIFYING ALL ABELIAN PERIODS OF A STRING IN QUADRATIC TIME AND RELEVANT PROBLEMS ⋮ Computing $\pi (x)$ analytically ⋮ Matching with don't-cares and a small number of mismatches ⋮ The complexity of class polynomial computation via floating point approximations ⋮ Faster pattern matching with character classes using prime number encoding ⋮ Two algorithms to find primes in patterns ⋮ Approximating the number of integers without large prime factors ⋮ Quadratic class numbers and character sums ⋮ An estimate for the number of integers without large prime factors ⋮ An improved sieve of Eratosthenes ⋮ New results for witnesses of Robin’s criterion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A space-efficient fast prime number sieve
• Explaining the wheel sieve
• Fast compact prime number sieves (among others)
• A sublinear additive sieve for finding prime number
• A linear algorithm for incremental digital display of circular arcs
• The segmented sieve of eratosthenes and primes in arithmetic progressions to 1012
• The First Occurrence of Large Gaps Between Successive Primes
• Experiments on the Lattice Problem of Gauss
• Algorithmic number theory. 4th international symposium. ANTS-IV, Leiden, the Netherlands, July 2--7, 2000. Proceedings