1,1

A number n is prime if it is greater than 1 and has no positive divisors except 1 and n.

A number n is prime if and only if it has exactly two divisors.

A prime has exactly one proper divisor, 1.

Not the sum of an odd number >1 of consecutive odd numbers. - Jon Perry (perry(AT)globalnet.co.uk), Sep 10 2004

Comment from Pieter Moree, Oct 14 2004: The paper by Kaoru Motose starts as follows: "Let q be a prime divisor of a Mersenne number 2^p-1 where p is prime. Then p is the order of 2 (mod q). Thus p is a divisor of q-1 and q>p. This shows that there exist infinitely many prime numbers."

1 is not a prime, for if the primes included 1, then the factorization of a natural number n into a product of primes would not be unique, since n = n*1.

Prime(n) and pi(n) are inverse functions: A000720(a(n)) = n, and a(n) is the least number m such that a(A000720(m)) = a(n). a(A000720(n)) = n if (and only if) n is prime.

Elementary primality test: If no prime =<sqrt(m) divides m, then m is prime.(since a prime is its own exclusive multiple, apart from 1) - Lekraj Beedassy (blekraj(AT)yahoo.com), Mar 31 2005

Second sequence ever computed by electronic computer, on EDSAC, May 9 1949 (see Renwick link). - Russ Cox (rsc(AT)swtch.com), Apr 20 2006

Every prime p is a linear combination of previous primes p(n) with nonzero coefficients c(n) and |c(n)| < p(n). - Amarnath Murthy, Franklin T. Adams-Watters and Joshau Zucker, May 17 2006.

Odd primes can only be written as a sum of two consecutive integers. Powers of 2 do not have a representation as a sum of k consecutive integers (other than the trivial n=n, for k=1). See A111774. - Jaap Spies (j.spies(AT)hccnet.nl), Jan 04 2007

There is a unique decomposition of the primes: provided the weight A117078(n) is > 0, we have prime(n) = weight * level + gap, or A000040(n) = A117078(n) * A117563(n) + A001223(n). - Remi Eismann (reismann(AT)free.fr), Feb 16 2007

M. Agrawal, N. Kayal and N. Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781-793.

M. Aigner and G. M. Ziegler, Proofs from The Book, Springer-Verlag, Berlin, 2nd. ed., 2001; see p. 3.

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.

E. Bach and J. O. Shallit, Algorithmic Number Theory, I, Chaps. 8, 9.

P. T. Bateman and H. G. Diamond, A hundred years of prime numbers, Amer. Math. Monthly, Vol. 103 (1996) pp. 729-741.

D. M. Bressoud, Factorization and Primality Testing, Springer-Verlag NY 1989.

R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 1.

J.-P. Delahaye, Merveilleux nombres premiers, Pour la Science-Belin Paris, 2000.

J.-P. Delahaye, Savoir si un nombre est premier: facile, Pour La Science, 303(1) 2003, pp. 98-102.

M. Dietzfelbinger, Primality Testing in Polynomial Time, Springer NY 2004.

J. Elie, "L'algorithme AKS", in 'Quadrature', No. 60, pp. 22-32, 2006 EDP-sciences, Les Ulis (France);

Seymour. B. Elk, "Prime Number Assignment to a Hexagonal Tessellation of a Plane That Generates Canonical Names for Peri-Condensed Polybenzenes", J. Chem. Inf. Comput. Sci., vol. 34 (1994), pp. 942-946.

W. & F. Ellison, Prime Numbers, Hermann Paris 1985

T. Estermann, Introduction to Modern Prime Number Theory, Camb. Univ. Press, 1969.

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 2.

H. D. Huskey, Derrick Henry Lehmer [1905-1991]. IEEE Ann. Hist. Comput. 17 (1995), no. 2, 64-68. Math. Rev. 96b:01035

M. N. Huxley, The Distribution of Prime Numbers, Oxford Univ. Press, 1972.

D. S. Jandu, Prime Numbers And Factorization, Infinite Bandwidth Publishing, N. Hollywood CA 2007.

E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Chelsea, NY, 1974.

D. H. Lehmer, The sieve problem for all-purpose computers. Math. Tables and Other Aids to Computation, Math. Tables and Other Aids to Computation, 7, (1953). 6-14. Math. Rev. 14:691e

D. N. Lehmer, "List of Prime Numbers from 1 to 10,006,721", Carnegie Institute, Washington, D.C. 1909.

W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, Chap. 6.

H. Lifchitz, Table Des nombres Premiers de 0 a 20 millions (Tomes I & II), Albert Blanchard, Paris 1971.

R. F. Lukes, C. D. Patterson and H. C. Williams, Numerical sieving devices: their history and some applications. Nieuw Arch. Wisk. (4) 13 (1995), no. 1, 113-139. Math. Rev. 96m:11082

Kaoru Motose, On values of cyclotomic polynomials. II, Math. J. Okayama Univ. 37 (1995), 27-36.

P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag NY 1995.

P. Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004.

H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhaeuser Boston, Cambridge MA 1994.

B. Rittaud, "31415879. Ce nombre est-il premier?" ['Is this number prime?'], La Recherche, Vol. 361, pp. 70-73, Feb 15 2003, Paris.

M. du Sautoy, The Music of the Primes, Fourth Estate / HarperCollins, 2003; see p. 5.

D. Shanks, Solved and Unsolved Problems in Number Theory, 2nd. ed., Chelsea, 1978, Chap. 1.

D. Wells, Prime Numbers:The Most Mysterious Figures In Math, J.Wiley NY 2005.

H. C. Williams, and J. O. Shallit, Factoring integers before computers. Mathematics of Computation 1943-1993: a half-century of computational mathematics (Vancouver, BC, 1993), 481-531, Proc. Sympos. Appl. Math., 48, AMS, Providence, RI, 1994. Math. Rev. 95m:11143

N. J. A. Sloane, Table of n, prime(n) for n = 1..10000

N. J. A. Sloane, Table of n, prime(n) for n = 1..100000

M. Agrawal, N. Kayal & N. Saxena, PRIMES is in P, Original Preprint; September 2005 Version

M. Agrawal, N. Kayal & N. Saxena, PRIMES is in P, Annals of Maths., 160 no.2 (2004) pp. 781-793

P. Alfeld, Notes and Literature on Prime Numbers

Anonymous, List of primes up to 10^6 [Broken link]

Anonymous, Prime Numbers (Applet)

Anonymous, Prime Number Master Index (for primes up to 2*10^7)

Anonymous, Primzahlenliste(Prime List Generator)

Anonymous, prime number

D. J. Bernstein, Proving Primality After Agrawal-Kayal-Saxena

D. J. Bernstein, Distinguishing prime numbers from composite numbers

P. Berrizbeitia, Sharpening "Primes is in P" for a large family of numbers

A. Booker, The Nth Prime Page

F. Bornemann, PRIMES Is in P:A Breakthrough for "Everyman"

A. Bowyer, Formulae for Primes

B. M. Bredikhin, Prime number

J. Brennan, Prime Number List Server

R. P. Brent, Primality testing and integer factorization

J. Britton, Prime Number List

D. Butler, The first 2000 Prime Numbers

C. K. Caldwell, The Prime Pages

C. K. Caldwell, Tables of primes

C. K. Caldwell, The first 10000 primes

C. K. Caldwell, A Primality Test

M. Chamness, Prime number generator (Applet)

J.-L. Cooke, Prime Numbers(Primality Tester)

P. Cox, Primes is in P

P. J. Davis & R. Hersh, The Mathematical Experience, The Prime Number Theorem

J.-P. Delahaye, Formules et nombres premiers

Desmatron, Primes 2 through 101477

J. Elie, L'algorithme AKS ou Les nombres premiers sont de classe P

C. P. Estany, List of (148933) Prime Numbers 1 through 2000000

L. Euler, Observations on a theorem of Fermat and others on looking at prime numbers

W. Fendt, Table of Primes from 1 to 1000000000000

P. Flajolet, S. Gerhold and B. Salvy, On the non-holonomic character of logarithms, powers, and the n-th prime function

J. Flamant, Primes up to one million

K. Ford, Expositions of the PRIMES is in P theorem.

L. & Y. Gallot, The Chronology of Prime Number Records

P. Garrett, Big Primes, Factoring Big Integers

P. Garrett, Naive Primality Test

P. Garrett, Listing Primes

N. Gast, PRIMES is in P: Manindra Agrawal, Neeraj Kayal and Nitin Saxena

D. A. Goldston, S. W. Graham, J. Pintz and C. Y. Yildirim, Small gaps between primes and almost primes

A. Granville, It Is Easy To Determine Whether A Given Number Is Prime

A. Granville, It is easy to determine whether a given integer is prime

P. Hartmann, Prime number proofs

ICON Project, List of first 50000 primes grouped within ten columns

N. Kayal & N. Saxena, Resonance 11-2002, A polynomial time algorithm to test if a number is prime or not

M.-H. Kim, Unsolved Problems In Number Theory

J.-M. De Koninck, Les nombres premiers: mysteres et consolation

J.-M. De Koninck, Nombres premiers: mysteres et enjeux

A. F. Labossiere, Sobalian Coefficients.

A. F. Labossiere, Miscellaneous.

E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, vol. 1 and vol. 2, Leipzig, Berlin, B. G. Teubner, 1909.

D. N. Lehmer, Table of the First 2500 Prime Numbers, Carnegie Institute of Washington,1914.

W. Liang & H. Yan, Pseudo Random test of prime numbers

J. Malkevitch, Primes

MathIsFun.com, Prime Numbers Chart

Mathworld Headline News, Primality Testing is Easy

K. Matthews, Generating prime numbers

Y. Motohashi, Prime numbers-your gems

J. Moyer, Some Prime Numbers

C. W. Neville, New Results on Primes from an Old Proof of Euler's

L. C. Noll, Prime numbers, Mersenne Primes, Perfect Numbers, etc.

J. J. O'Connor & E. F. Robertson, Prime Numbers

M. Ogihara & S. Radziszowski, Agrawal-Kayal-Saxena Algorithm for Testing Primality in Polynomial Time

J. M. Parganin, Primes less than 50000

K. Peavey, Prime List Display in batches of 50000

I. Peterson, Prime Pursuits

O. E. Pol, Numeros primos

O. E. Pol, Illustration of initial terms.

Prime-Numbers.org, Prime-Numbers.org(Prime Tester & List Server)

Primefan, The First 500 Prime Numbers

Primefan, Script to Calculate Prime Numbers

Project Gutenberg Etext, First 100000 Prime Numbers

C. D. Pruitt, Formulae for Generating All Prime Numbers

R. Ramachandran, Frontline 19 (17) 08-2000, A Prime Solution

W. S. Renwick, EDSAC log.

F. Richman, Generating primes by the sieve of Eratosthenes

S. M. Ruiz and J. Sondow, Formulas for pi(n) and the n-th prime.

S. O. S. Math, First 1000 Prime Numbers

A. Schulman, Prime Number Calculator

M. Slone, PlanetMath.Org, First thousand positive prime numbers

A. Stiglic, The PRIMES is in P little FAQ

S. Stepney, Primes 2 through 10000

J. Teitelbaum, Review of "Prime numbers:A computational perspective" by R.Crandall & C.Pomerance

K. Thomas, Prime Numbers

J. Thonnard, Les nombres premiers(Primality check; Closest next prime; Factorizer)

A. Turpel, Aesthetics of the Prime Sequence

G. Villemin's Almanach of Numbers, Nombres Premiers

G. Villemin's Almanac of Numbers, Primes up to 10000

S. Wagon, Prime Time : Review of "Prime Numbers:A Computational Perspective" by R. Crandall & C. Pomerance

M. R. Watkins, unusual and physical methods for finding prime numbers

S. Wedeniwski, Primality Tests on Commutator Curves

E. Wegrzynowski, Les formules simples qui donnent des nombres premiers en grande quantites

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (1).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (2).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (3).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (4)

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (5)

Wikipedia, Prime number

D. Williams, Prime Generator(between two bounds)

G. Xiao, Primes server, Sequential Batches Primes Listing (up to orders not exceeding 10^308)

G. Xiao, Numerical Calculator, To display p(n) for n up to 41561, operate on "prime(n)"

Z. Zheng, "Show Prime Numbers" server [p(n),n=1 up to 10^10] [Broken link?]

Index entries for "core" sequences

The prime number theorem is the statement that a(n) ~ n * log n as n -> infinity (Hardy and Wright, page 10).

a(n) = 2 + sum_{k=2..floor(2n*log(n)+2)} (1-floor(pi(k)/n)), for n>1, where the formula for pi(k) is given in A000720 (Ruiz and Sondow 2002) - Jonat han Sondow (jsondow(AT)alumni.princeton.edu), Mar 06 2004

I conjecture that Sum(1/(p(i)*log(p(i)))=Pi/2=1.570796327... Sum(1/(i=1..100000 p(i)*log(p(i)))=1.565585514... It converges very slowly. - Miklos Kristof (kristmikl(AT)freemail.hu), Feb 12 2007

A000040 := n->ithprime(n); [ seq(ithprime(i), i=1..100) ];

Table[ Prime[n], {n, 1, 60} ]

(MAGMA) [ n : n in [2..500] | IsPrime(n) ];

(MAGMA) a := func< n | NthPrime(n) >;

(PARI) a(n)=if(n<1, 0, prime(n))

# (SAGE) Demonstration program from Jaap Spies:

# To see which functions are available type: sloane.A[tab]

# All builtin SAGE programs are called the same way:

# a = sloane.A000040; a # This returns the name of the sequence

# a(n) # This returns the n-th number of the sequence:

# a.list(n) # This returns a list of the first n numbers:

# Copy and paste the following into a worksheet or the interpreter:

a = sloane.A000040; print a

print a(1)

print a(2)

print a(58)

print a.list(58)

Cf. A000027, A018252, A002808, A008578, A006879, A006880.

Cf. also A000720 ("pi"), A001223 (differences between primes), A001358 ("semiprimes").

Adjacent sequences: A000037 A000038 A000039 this_sequence A000041 A000042 A000043

Sequence in context: A052424 A055398 A070159 this_sequence A008578 A100726 A015919

core,nonn,nice,easy

njas

Additional links contributed by Lekraj Beedassy (blekraj(AT)yahoo.com), Dec 23 2003

Additional comments from Jonathan Sondow (jsondow(AT)alumni.princeton.edu), Dec 27 2004