A prime number is a whole number greater than 1, whose only two whole-number factors are 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.

As we proceed in the set of natural numbers * N* = {1, 2, 3, ...}, the
primes become less and less frequent in general. However, there is no largest prime
number. For every prime number

*p*, there exists a prime number

*p*' such that

*p*' is greater than

*p*. This was demonstrated in ancient times by the Greek mathematician Euclid.

Suppose *n* is a whole number, and we want to test it to see if it is prime.
First, we take the square root (or the 1/2 power) of *n*; then we round this number up to
the next highest whole number. Call the result *m*. We must find all of the
following quotients:

*q _{m}* =

*n*/

*m*

*q*

_{(m-1)}=

*n*/ (

*m*-1)

*q*

_{(m-2)}=

*n*/ (

*m*-2)

*q*

_{(m-3)}=

*n*/ (

*m*-3)

**. . .**

*q*

_{3}=

*n*/ 3

*q*

_{2}=

*n*/ 2

The number *n* is prime if and only if none of the *q*'s, as derived above, are
whole numbers.

A computer can be used to test extremely large numbers to see if they are prime. But, because there is no limit to how large a natural number can be, there is always a point where testing in this manner becomes too great a task even for the most powerful supercomputers. Various algorithms have been formulated in an attempt to generate ever-larger prime numbers. These schemes all have limitations.

A Mersenne
prime must be reducible to the form 2 * ^{n}* - 1,
where

*n*is a prime number. The first few known values of

*n*that produce Mersenne primes are where

*n*= 2,

*n*= 3,

*n*= 5,

*n*= 7,

*n*= 13,

*n*= 17,

*n*= 19,

*n*= 31,

*n*= 61, and

*n*= 89.

A Fermat prime is a Fermat
number that is also a prime number . A Fermat
number *F _{n}* is of the form 2

*+ 1, where*

^{m}*m*is the

*n*th power of 2 (that is,

*m*= 2

*, where*

^{n}*n*is an integer).

*This was last updated in*June 2015

*Posted by:*Margaret Rouse

## Tech TalkComment

## Share

## Comments

## Results

## Contribute to the conversation