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.

*This was last updated in*May 2008

*Posted by:*Margaret Rouse

## Tech TalkComment

## Share

## Comments

## Results

## Contribute to the conversation