A prime number (or prime integer, often simply called a "prime" for short) is a positive integer p > 1 that has no positive integer divisors other than 1 and p itself. (More concisely, a prime number p is a positive integer having exactly one positive divisor other than 1.) For example, the only divisors of 13 are 1 and 13, making 13 a prime number, while the number 24 has divisors 1, 2, 3, 4, 6, 8, 12, and 24 (corresponding to the factorization ), making 24 not a prime number. Positive integers other than 1 which are not prime are called composite numbers.

The number 1 is a special case which is considered neither prime nor composite (Wells 1986, p. 31). Although the number 1 used to be considered a prime (Goldbach 1742; Lehmer 1909; Lehmer 1914; Hardy and Wright 1979, p. 11; Gardner 1984, pp. 86-87; Sloane and Plouffe 1995, p. 33; Hardy 1999, p. 46), it requires special treatment in so many definitions and applications involving primes greater than or equal to 2 that it is usually placed into a class of its own. A good reason not to call 1 a prime number is that if 1 were prime, then the statement of the fundamental theorem of arithmetic would have to be modified since "in exactly one way" would be false because any . In other words, unique factorization into a product of primes would fail if the primes included 1. A slightly less illuminating but mathematically correct reason is noted by Tietze (1965, p. 2), who states "Why is the number 1 made an exception? This is a problem that schoolboys often argue about, but since it is a question of definition, it is not arguable." As more simply noted by Derbyshire (2004, p. 33), "On balance, 2 pays its way [as a prime] on balance; 1 doesn't."

With 1 excluded, the smallest prime is therefore 2. However, since 2 is the only even prime, it is also somewhat special, and the set of all primes excluding 2 is therefore called the "odd primes." Note also that while 2 is considered a prime today, at one time it was not (Tietze 1965, p. 18; Tropfke 1921, p. 96).

The nth prime number is commonly denoted , so , , and so on, and may be computed in Mathematica as Prime[n].

The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ... (Sloane's A000040; Hardy and Wright 1979, p. 3), and the set of primes is sometimes denoted , represented in Mathematica as Primes.

The first few primes are illustrated above as a sequence of binary bits.

Euler commented "Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate" (Havil 2003, p. 163).

In a 1975 lecture, D. Zagier commented "There are two facts about the distribution of prime numbers of which I hope to convince you so overwhelmingly that they will be permanently engraved in your hearts. The first is that, despite their simple definition and role as the building blocks of the natural numbers, the prime numbers grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behavior, and that they obey these laws with almost military precision" (Havil 2003, p. 171).

The th prime for n = 0, 1, ... is given by 2, 29, 541, 7919, 104729, 1299709, 15485863, 179424673, 2038074743, ... (Sloane's A006988; Graham et al. 1990, p. 111).

Large primes (Caldwell) include the large Mersenne primes, Ferrier's prime, and the -digit counterexample showing that 5359 is not a Sierpinski Number of the Second Kind (Helm and Norris). The largest known prime as of June 2004 is the Mersenne prime (Weisstein 2004).

Prime numbers can be generated by sieving processes (such as the sieve of Eratosthenes), and lucky numbers, which are also generated by sieving, appear to share some interesting asymptotic properties with the primes. Prime numbers satisfy many strange and wonderful properties. Although there exist explicit prime formulas (i.e., formulas which either generate primes for all values or else the nth prime as a function of n), they are contrived to such an extent that they are of little practical value.

While the term "prime number" commonly refers to prime positive integers, other types of primes are also defined, such as the Gaussian primes.

The function which gives the number of primes less than or equal to a number n is denoted and is called the prime counting function. The theorem giving an asymptotic form for is called the prime number theorem. Similarly, the numbers of primes of the form less than or equal to a number n is denoted and is called the modular prime counting function.

Many prime factorization algorithms have been devised for determining the prime factors of a given integer, a process known as factorization or prime factorization. They vary quite a bit in sophistication and complexity. It is very difficult to build a general-purpose algorithm for this computationally "hard" problem, so any additional information which is known about the number in question or its factors can often be used to save a large amount of time. It should be emphasized that although no efficient algorithms are known for factoring arbitrary integers, it has not been proved that no such algorithm exists. It is therefore conceivable that a suitably clever person could devise a general method of factoring which would render the vast majority of encryption schemes in current widespread use, including those used by banks and governments, easily breakable.

Because of their importance in encryption algorithms such as RSA encryption, prime numbers can be important commercial commodities. In fact, R. Schlafly (1994) has obtained U.S. Patent on the following two primes (expressed in hexadecimal notation):

and

The fundamental theorem of arithmetic states that any positive integer can be represented in exactly one way as a product of primes. Euclid's second theorem demonstrated that there are an infinite number of primes. However, it is not known if there are an infinite number of primes of the form (Hardy and Wright 1979, p. 19; Ribenboim 1996, pp. 206-208), whether there are an infinite number of twin primes (the twin prime conjecture), or if a prime can always be found between and (Hardy and Wright 1979, p. 415; Ribenboim 1996, pp. 397-398). The latter two of these are two of Landau's problems.

The simplest method of finding factors is so-called "direct search factorization" (a.k.a. trial division). In this method, all possible factors are systematically tested using trial division to see if they actually divide the given number. It is practical only for very small numbers. More general (and complicated) methods include the elliptic curve factorization method and number field sieve factorization method.

It has been proven that the set of prime numbers is a Diophantine set (Ribenboim 1991, pp. 106-107).

With the exception of 2 and 3, all primes are of the form , i.e., (Wells 1986, p. 68). For n an integer , n is prime iff the congruence equation

holds for k = 0, 1, ..., (Deutsch 1996), where is a binomial coefficient. In addition, an integer n is prime iff

The first few composite n for which are n = 312, 560, 588, 1400, 23760, ... (Sloane's A011774; Guy 1997), with a total of 18 such numbers less than .

Cheng (1979) showed that for x sufficiently large, there always exist at least two primes between and x for (Le Lionnais 1983, p. 26). In practice, this relation seems to hold for all x > 2521.

Primes consisting of consecutive digits (counting 0 as coming after 9) include 2, 3, 5, 7, 23, 67, 89, 4567, 78901, ... (Sloane's A006510). Primes consisting of digits that are themselves primes include 23, 37, 53, 73, 223, 227, 233, 257, 277, 337, 353, 373, 523, 557, ... (Sloane's A019546), which is one of the Smarandache sequences.

Almost Prime, Composite Number, Divisor, Good Prime, Home Prime, Irregular Prime, Long Prime, Primary, Prime Factorization Algorithms, Prime Formulas, Prime Number Theorem, Prime Power Symbol, Prime Products, Prime String, Prime Sums, Primorial, Probable Prime, Pseudoprime, Regular Prime, Semiprime, Smooth Number, Titanic Prime, Twin Primes

http://functions.wolfram.com/NumberTheoryFunctions/Prime/