A prime prime primer 4 0 0 Michael Caola 2 6 Normanton Rd., Bristol, BS8 2TY, U.K. n [email protected] a J 6 February 8, 2008 ] O Abstract H Wepresentasimple,closedformulawhichgivesalltheprimesinorder. . It is a simple product of integer floor and ceiling functions. h t a m 1 Introduction [ Interest in prime numbers continues apace, e.g. computing, secure commu- 1 nications, quantum computing, statistical physics, engineering and, of course, v mathematics. However,wearestillfarfromfindingausefulfunctionp(n)which 3 4 generates all the primes in order. We present such a function next and discuss 0 its usefulness [1]. All variables below, save x, are integers. 1 0 4 2 Analysis 0 / h Consider the product function t a √n m ⌊ ⌋ n n p(n)= − , (1) v: nY′=2(cid:18)(cid:24)n′(cid:25) (cid:22)n′(cid:23)(cid:19) i where the integer floor ⌊x⌋ (ceiling ⌈x⌉) functions give the greatest (smallest) X integer not greater (not smaller) than x: e.g. ⌊7⌋ = ⌈7⌉ = 7, ⌊3.7⌋ = 3, r a ⌈3.7⌉=4, ⌈−7.3⌉=−7, ⌊−7.3⌋=−8. Then, for n=2,3,4..., 1, if n is prime p(n)= (2) (cid:26) 0, if not Also,wehavedirectlyfrom(2)thatthenumberπ(n)ofprimesnotexceeding n is n π(n)= p(n′) (3) nX′=1 1 3 Discussion • That function (1) satisfies (2) may be seen by inspection of ⌈⌉ - ⌊⌋: 0, if x is an integer ⌈x⌉−⌊x⌋= (4) (cid:26) 1, if not Thus p(n) = 1 only if all the divisors n of n give non-zero remaninders, ′ which is the definition of primality. • What constitutes a “useful function” p(n) is partly subjective [1], so we describe our p(n) as: simple, compact, transparent, and using only two basic notions (floor ⌊⌋) and (ceiling ⌈⌉) of integer mathematics. • We have programmedand checked algorithm (1,2,3) on a PC. Reference [1] Hardy, G. H. & Wright, E. M. (1978) ’An introduction to the theory of numbers’, ( 5th edition). Clarendon Press, Oxford. 2