# Mathematics for Programmers 1 :Prime Numbers

Posted April 13, 2007

on:- In: Math | Programming
- Leave a Comment

A prime number (or prime integer, often simply called a “prime” for short) is a positive integer 1″ border=”0″ height=”15″ width=”33″> that has no positive integer divisors other than 1 and itself. (More concisely, a prime number 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.

Prime numbers are therefore numbers that cannot be factored or, more precisely, are numbers whose divisors are trivial and given by exactly 1 and .

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), “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 (which, ironically, in some sense makes it the “oddest” 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 th prime number is commonly denoted , so , , and so on.

The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, …

A mnemonic for remembering the first seven primes is, “In the early morning, astronomers spiritualized nonmathematicians”

In the Season 1 episode “Prime Suspect” (2005) of the television crime drama *NUMB3RS*, math genius Charlie Eppes realized that character Ethan’s daughter has been kidnapped because he is close to solving the Riemann hypothesis, which allegedly would allow the perpetrators to break essentially all internet security by factoring large numbers.

The numbers of decimal digits in for , 1, … is given by 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, …

Source :http://mathworld.wolfram.com

## Leave a Reply