My Thoughts & Views

Mathematics for Programmers 1 :Prime Numbers

Posted on: April 13, 2007

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 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 24==2^3.3), 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 n whose divisors are trivial and given by exactly 1 and n.

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 n==n.1. 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 nth prime number is commonly denoted p_n, so p_1==2, p_2==3, 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 p_(10^n) for n==0, 1, … is given by 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, …

Source :


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: