prime numberA 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:
qm = n / m
q(m-1) = n / (m-1)
q(m-2) = n / (m-2)
q(m-3) = n / (m-3)
. . .
q3 = n / 3
q2 = 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.
|
|
|
| Last updated on:
May 07, 2008 |
|
|
Overheard
"In a matter of days, Mr. Spitzer went from potential presidential candidate to — in the tech world, at least — the poster boy for software usually used to snare fraudsters, money launderers and terrorists."
|
|
|
|
|
