Primality test and primes enumeration using odd numbers indexation




odd number index, primality test, primes enumeration, Atkin sieve, composite odd numbers, wheel sieve


Odd numbers can be indexed by the map k(n)=(n-3)⁄2,n∈2N+3. We first propose a basic primality test using this index function that was first introduced in [8]. Input size of operations is reduced which improves computational time by a constant. We then apply similar techniques to Atkin’s prime-numbers sieve which uses modulus operations and finally to Pritchard’s wheel sieve, in both case yielding similar results.


(1) René SCHOOF (2008), Four primality testing algorithms. Algorithmic Number Theory, MSRI Publications, Volume 44.

(2) Manindra AGRAWAL, Neeraj KAYAL, Nitin SAXENA (2004), PRIMES is in P. Ann. of Math. (2) 160, No. 2, pp. 781-793. MR2123939 (2006a:11170).

(3) Paul PRITCHARD (1981), A sublinear additive sieve for finding prime numbers. Communications of the ACM 24(1), pp. 18-23.

(4) Paul PRITCHARD (1982), Explaining the Wheel Sieve. Acta Informatica 17, pp. 477-485.

(5) Paul PRITCHARD (1994), Improved Incremental Prime Number Sieves. Algorithmic Number Theory Symposium. pp. 280–288. CiteSeerX

(6) Arthur ATKIN AND Daniel BERNSTEIN (2003), Prime sieves using binary quadratic forms. Mathematics of Computation Volume 73, Number 246, pp. 1023-1030.

(7) Gabriel PAILLARD, Felipe FRANCA, Christian LAVAULT (2013), A distributed wheel sieve algorithm using Scheduling by Multiple Edge Reversal. HAL-00794389.

(8) Marc WOLF, François WOLF (2018), Representation theorem of composite odd numbers indices. SCIREA Journal of Mathematics, Vol. 3, pp. 106-117.

(9) Marc WOLF, François WOLF, Corentin LE COZ (2018), Calculation of extended gcd by normalization. SCIREA Journal of Mathematics. Vol. 3, pp. 118-131.




How to Cite

Wolf, M., & François, W. (2020). Primality test and primes enumeration using odd numbers indexation. Transactions on Engineering and Computing Sciences, 8(2), 11–41.