Prime sieves using binary quadratic forms
The problem of listing all the prime numbers up to a fixed bound \(N\) is very old going back, at least, to the classic sieve of Eratostenes. \textit{P. Pritchard} [J. Algorithms 4, 332--344 (1983; Zbl 0546.10004)] posed the question of the existence of an algorithm able to find such a listing using \(o(N)\) operations (loads, stores, comparisons, additions and subtractions of \(O(\log N))\) - bits integers) and \(O(N^{\alpha})\) bits of memory for some \(\alpha < 1\). The present paper gives an affirmative answer to this question. The tool used is the enumeration of the values taken by certain integral binary quadratic forms. As the authors point out, in the language of quadratic forms, the sieve of Eratosthenes can be interpreted as the enumeration of the natural numbers represented by the reducible quadratic form \(xy\). They consider instead some irreducible binary quadratic forms. More concretely they consider the three following quadratic forms: \(4x^2+y^2\) for the primes \(p\equiv 1 \bmod 4\), \(3x^2+y^2\) for the primes \(p\equiv 7 \bmod 12\)\, and \(3x^2+y^2\) for the primes \(p\equiv 11 \bmod 12\)\, (as the authors point out many other choices are possible). The algorithm uses the propriety that, in the three cases, a natural number \(n\) is prime if and only if the number of positive representations \((x,y)\) of \(n\) (and \(x>y>0\) in the third case) is odd. The resulting algorithm uses \(O(N/\log\log N)\) operations and \(N^{1/2+o(1)}\) bits of memory. The authors also point out a later improvement of W. F. Galway that needs only \(N^{1/3+o(1)}\) bits of memory.
- A linear algorithm for incremental digital display of circular arcs
- A space-efficient fast prime number sieve
- A sublinear additive sieve for finding prime number
- Algorithmic number theory. 4th international symposium. ANTS-IV, Leiden, the Netherlands, July 2--7, 2000. Proceedings
- Dissecting a sieve to cut its need for space
- Experiments on the Lattice Problem of Gauss
- Explaining the wheel sieve
- Fast compact prime number sieves (among others)
- scientific article; zbMATH DE number 3657869 (Why is no real title available?)
- scientific article; zbMATH DE number 44590 (Why is no real title available?)
- scientific article; zbMATH DE number 1787206 (Why is no real title available?)
- scientific article; zbMATH DE number 3036407 (Why is no real title available?)
- The First Occurrence of Large Gaps Between Successive Primes
- The segmented sieve of eratosthenes and primes in arithmetic progressions to 1012
- Faster pattern matching with character classes using prime number encoding
- Bits and relative order from residues, space efficiently
- Pattern matching with wildcards using words of shorter length
- Dissecting a sieve to cut its need for space
- The complexity of class polynomial computation via floating point approximations
- Approximating the number of integers without large prime factors
- Two compact incremental prime sieves
- Primes at a Glance
- 65.33 The Computation of Prime Numbers by Gandhi's Formula for the nth Prime
- An estimate for the number of integers without large prime factors
- scientific article; zbMATH DE number 780073 (Why is no real title available?)
- Identifying all abelian periods of a string in quadratic time and relevant problems
- Two algorithms to find primes in patterns
- New results for witnesses of Robin's criterion
- ON THE COMPLEXITY OF COMPUTING PRIME TABLES ON THE TURING MACHINE
- Computing (x) analytically
- An improved sieve of Eratosthenes
- Empirical verification of the even Goldbach conjecture and computation of prime gaps up to 4⋅10¹⁸
- Quadratic class numbers and character sums
- \textsc{Rings}: an efficient Java/Scala library for polynomial rings
- Complexity of limit cycles with block-sequential update schedules in conjunctive networks
- Algorithms and bounds on the sums of powers of consecutive primes
- An algorithm and computation to verify Legendre's conjecture up to \(7\cdot 10^{13}\)
- Reducing the space used by the sieve of Eratosthenes when factoring
- Phylogenetic network diversity parameterized by reticulation number and beyond
- Explicit bounds and parallel algorithms for counting multiply gleeful numbers
- Analysis of algorithms for Moser's problems on sums of consecutive primes
- Matching with don't-cares and a small number of mismatches
This page was built for publication: Prime sieves using binary quadratic forms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4452178)
