Algorithms 402: Increasing the efficiency of quicksort
M. H. van Emden · Communications of the ACM · 1970
The procedure generates the complex prime numbers located in the one-eighth plane defined by 0 2. PR and PI will contain respectively the real and imaginary parts of the generated list, with PR _> PI > 0 for each prime.The value of the procedure is the number of primes generated.Algorithm 311 [1], sieve 2, is used to generate the rational primes less than mL Then it is known (see, for instance [2]) that a rational prime p of the form p = 4n -b 1 can be expressed as p = a 2 -4-b 2, and factorized as (a+bi)(a--bi) in the complex plane, where a + bi and a -bi are complex primes.For our present purpose we choose a > b and include only a 4-bi in the list.A rational prime p of the form p = 4n + 3 remains prime in the complex plane, so we include p + 0i in the list if p < m.Finally, the complex prime 1 + i may be thought of as one of the factors of the remaining rational prime 2 = (1+i)(1-i).Although this algorithm and Algorithm 372 [3] are not directly comparable, since they produce the list of complex primes in a different order, the accompanying remark suggests that the present algorithm is often to be preferred.REFERENCES : 1. CHARTRES, B.A. Algorithm 311, Prime number generator 2.